题目描述
小Q管理着一个大团队，大团队中有n个人,m个小团队，已知你每一个小团队里面的人数和每个人的编号（编号范围是0~n-1,—个人可能属于多个小团队，也有人可能一个小团队都不属于。），现在小Q会下达—个通知给编号为0的人，所有和编号为0的人同属某个小团体的人都会通过编号为0的人知晓这个通知，知晓通知的人会接着传达通知给自已小团队中的其他人。现在问你—共有多少个人知晓了通知（包括编号为0的人).
输入描述 输入第一行两个数n和m，代表n个人，m个小团体 接下来m行，每一行第一个数先输入一个x，代表这个小团队有x个人，后面跟着x个数，代表这个小团队里面人的编号 1 <= n <= 100000 1 <=m <= 500 1 <=x <=100
输出描述 对于每组测试数据：请输出一个答案代表知晓了通知的人数。
输入 10 3 2 0 1 5 6 5 3 2 7 2 6 1
输出 7
思路：并查集 #include<iostream> using namespace std; const int MAXN = 100000+5; int f[MAXN]; int Find(int x){ if(x==f[x]) return x; return f[x]=Find(f[x]); } void Union(int x,int y){ x=Find(x); y=Find(y); if(x!=y) { f[y]=x; } } int main() { int n,m,x,y,z; cin>>n>>m; for(int i=0;i<=n;i++){ f[i]=i; } for(int i=0;i<m;i++){ cin>>x; cin>>y; for(int i=1;i<x;i++){ cin>>z; Union(y,z); } } int res=0; int start = Find(0); for(int i=0;i<=n;i++){ if(Find(i)==start){ res++; } } cout<<res<<endl; return 0; }