1419 2022. 09. 09 12:14:02 kicsiboglar Sportos nyaralás cpp11 Elfogadva 40/40 98ms 24088 KiB 
#include <iostream>
#include <vector>
#include <deque>
#include <map>

#define ll long long 

using namespace std;

ll n,i,a,mini=9999999,b,k;
struct element
{
    bool seen=false;
    vector <ll> bike,kayak;
    ll compbike,compk;
};
vector <element> x;
vector <ll> res;

void BFS (ll start,bool id)
{
    deque<ll> v;
    v.push_back(start);
    x[start].seen=true;
    ll curr;
    while (!v.empty())
    {
        curr=v[0];
        v.pop_front();
        if (id)
        {
            for (auto &e:x[curr].bike)
            {
                if (!x[e].seen)
                {
                    x[e].seen=true;
                    x[e].compbike=x[curr].compbike;
                    v.push_back(e);

                }
            }
        }
        else
        {
            for (auto &e:x[curr].kayak)
            {
                if (!x[e].seen)
                {
                    x[e].seen=true;
                    x[e].compk=x[curr].compk;
                    /*if (x[e].compbike==x[curr].compbike&&x[curr].compbike!=0)
                    {
                        res[e]++;
                        res[curr]++;
                    }*/
                    v.push_back(e);

                }
            }
        }
    }
}



int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin>>n>>b>>k;
    x.resize(n+1);
    ll p,q;
    res.resize(n+1);
    for (i=1;i<=b;++i)
    {
        cin>>p>>q;
        x[p].bike.push_back(q);
        x[q].bike.push_back(p);
    }
    for (i=1;i<=k;++i)
    {
        cin>>p>>q;
        x[p].kayak.push_back(q);
        x[q].kayak.push_back(p);
    }

    ll nr=0;
    for (i=1;i<=n;++i)
    {
        if (!x[i].seen)
        {
            nr++;
            x[i].compbike=nr;
            BFS(i,true);
        }
    }
    for (i=1;i<=n;++i) x[i].seen=false;
    nr=0;

    for (i=1;i<=n;++i)
    {
        if(!x[i].seen)
        {
            nr++;
            x[i].compk=nr;
            BFS(i,false);
        }
    }
    map <pair<ll,ll> ,ll >components;
    pair<ll,ll> id;
    for (i=1;i<=n;++i) 
    {
        id.first=x[i].compbike;
        id.second=x[i].compk;
        components[id]++;
    }
   /* ll j;
    for (i=1;i<n;++i)
    {
        for (j=i+1;j<=n;++j)
        {
            if (x[i].compbike!=0&&x[i].compk!=0)
            {
                if (x[i].compbike==x[j].compbike&&x[i].compk==x[j].compk)
                {
                    res[i]++;
                    res[j]++;
                }
            }
        }
    }*/

    for (i=1;i<=n;++i) 
    {
        id.first=x[i].compbike;
        id.second=x[i].compk;
        cout<<components[id]-1<<" ";
    }
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 40/40
1 Elfogadva 0/0 3ms 1896 KiB
2 Elfogadva 0/0 86ms 21484 KiB
3 Elfogadva 1/1 2ms 2328 KiB
4 Elfogadva 1/1 2ms 2432 KiB
5 Elfogadva 1/1 2ms 2624 KiB
6 Elfogadva 1/1 2ms 2824 KiB
7 Elfogadva 1/1 2ms 2908 KiB
8 Elfogadva 1/1 2ms 3008 KiB
9 Elfogadva 1/1 2ms 2972 KiB
10 Elfogadva 1/1 3ms 3356 KiB
11 Elfogadva 2/2 3ms 3296 KiB
12 Elfogadva 2/2 4ms 3520 KiB
13 Elfogadva 2/2 8ms 4780 KiB
14 Elfogadva 2/2 7ms 4404 KiB
15 Elfogadva 2/2 37ms 13440 KiB
16 Elfogadva 2/2 50ms 17076 KiB
17 Elfogadva 3/3 64ms 20636 KiB
18 Elfogadva 3/3 64ms 20488 KiB
19 Elfogadva 2/2 45ms 13856 KiB
20 Elfogadva 2/2 59ms 17804 KiB
21 Elfogadva 2/2 75ms 20624 KiB
22 Elfogadva 2/2 71ms 21128 KiB
23 Elfogadva 3/3 86ms 21860 KiB
24 Elfogadva 3/3 98ms 24088 KiB