CCCC L2-024 部落【并查集】

https://www.patest.cn/contests/gplt/L2-024

首先在一行中输出这个社区的总人数、以及互不相交的部落的个数。随后对每一次查询，如果他们属于同一个部落，则在一行中输出“Y”，否则输出“N”。

/*

求连通分量，先记录下原始的连通分量，每删除一个点，删去相应的边（这里用邻接矩阵便于删除边），然后再重新统计连通分量。如果和原来相同（占领的点本身是孤立的点）或者比原来多1，都不是关键城市，如果删除一个点后所计算的连通分量比原来多两个或者两个以上则发出警报，最后如果删掉的点数和总的点数相同，打印Game Over。

*/

#include <bits/stdc++.h>

using namespace std;

const int maxn=;

int fa[maxn];

int cnt[maxn];

void init(){

    for (int i=;i<=;i++){

        fa[i]=i;

    }

}

int find(int x){

    if (x==fa[x]) return x;

    return fa[x]=find(fa[x]);

}

void unite(int x,int y){

    x=find(x);

    y=find(y);

    if (x==y) return;

    fa[y]=x;

}

bool same(int x,int y){

    return find(x)==find(y);

}

int main(){

    set<int> s;

    init();

    int n;

    cin >> n;

    for (int i=;i<n;i++){

        int k;

        cin >> k;

        int a;

        cin >> a;

        s.insert(a);

        for (int j=;j<k;j++){

            int b;

            cin >> b;

            s.insert(b);

            unite(a,b);

        }

    }

    int sum1=,sum2=;

    for (int i=;i<=s.size();i++){

            if (fa[i]==i) sum2++;

        }

    cout << s.size() << " " << sum2 <<endl;

    cin >> n;

    for (int i=;i<n;i++){

        int x,y;

        cin >> x >>y;

        if (same(x,y)){

            cout << "Y" << endl;

        }

        else{

            cout << "N" << endl;

        }

    }

}