526互联

abc049d <并查集>

发布时间 2023-06-20 19:05:22作者: O2iginal

https://atcoder.jp/contests/abc049/tasks/arc065_b

//  https://atcoder.jp/contests/abc049/tasks/arc065_b
// 使用两个并查集维护连通关系
// 求并集, 使用每个并查集的祖宗节点组成的pair表示这个交集
#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
int f1[N], f2[N];
int num[N];

int find(int f[], int x)
{
    if (x != f[x]) f[x] = find(f, f[x]);
    return f[x];
}

void solv()
{
    int n, k, l;
    cin >> n >> k >> l;
    for (int i = 1; i <= n; i ++) f1[i] = f2[i] = i;
    int a, b;
    for (int i = 1; i <= k; i ++)
    {
        cin >> a >> b;
        int fa = find(f1, a), fb = find(f1, b);
        f1[fa] = fb;
    }

    for (int i = 1; i <= l; i ++)
    {
        cin >> a >> b;
        int fa = find(f2, a), fb = find(f2, b);
        f2[fa] = fb;
    }

    map<pair<int, int>, int> mp;

    for (int i = 1; i <= n; i ++) mp[{find(f1, i), find(f2, i)}] ++;
    for (int i = 1; i <= n; i ++) cout << mp[{find(f1, i), find(f2, i)}] << ' ';
}

int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int T = 1;
    // cin >> T;
    while (T --)
    {
        solv();
    }
    return 0;
}