观察样例，发现A、B、C三人，即使A和C并没有共同爱好，但他们和B都有共同爱好，所以他们也属于同一个集合
因此我考虑将有关联的爱好捆绑在一起：合并一个人的所有爱好，只要A和B的爱好有交集，那么他们的所有爱好都会被绑定到一个集合中
统计人数时，取每个人的第一个爱好（题目保证每个人至少一个爱好），找到该爱好所属的集合的根，将根的值放入result,累加一次num[r]；最后将每个集合对应的人数放入out，排序一下输出即可
但是提交后发现，1、4样例无法通过，检查了半天思路并没有问题啊...很纳闷，最后无意中看到合并操作时打字打错了，本来应该是当两个节点不属于一个集合中时，令b的根指向a（纯属打字错误，给自己长个记性，敲的时候一定要多检查，等全写好了，错在哪里都不知道....）
#include<iostream> #include<vector> #include<algorithm> using namespace std; int father[1005]; int num[1005]={0}; int ff(int a) { int x=a; while(a!=father[a]) { a=father[a]; } while(x!=father[x]) { int c=x;x=father[x];father[c]=a; } return a; } void nion(int a,int b) { int fa=ff(a),fb=ff(b); if(fa!=fb)father[fb]=a; } int main() { int n,k; cin>>n; vector<int> v[1005]; for(int i=0;i<1005;i++)father[i]=i; for(int i=1;i<=n;i++) { cin>>k; int temp,p; getchar(); cin>>temp; v[i].push_back(temp); for(int j=1;j<k;j++) { cin>>p; nion(temp,p); } } vector<int> result,out;//result存储每个根节点下标 for(int i=1;i<=n;i++) { int r=ff(v[i][0]); if(num[r]==0)result.push_back(r); num[r]++; } for(int i=0;i<result.size();i++)out.push_back(num[result[i]]); sort(out.begin(),out.end()); cout<<result.size()<<endl; for(int i=out.size()-1;i>=0;i--) { if(i!=0)cout<<out[i]<<" "; else cout<<out[i]<<endl; } return 0; }
