A1107

//并查集 #include<iostream> #include<algorithm> using namespace std; //用 const int maxn=1001; int n,course[maxn]={0},father[maxn],isRoot[maxn]={0}; bool cmp(int a, int b) { return a>b; } void init() { for(int i=1; i<=n; i++) { father[i]=i; } } int findFather(int x) { while(x!=father[x]) x=father[x]; return x; } void Union(int a, int b) { int faA=findFather(a); int faB=findFather(b); if(faA!=faB) father[faA]=faB; } int main() { cin >> n; init(); int temp,temp1; for(int i=1; i<=n; i++) { scanf("%d:",&temp); //输入循环的次数 for(int j=0; j<temp; j++) { cin >> temp1; if(course[temp1]==0) //如果课程对应的数值为0，则重新标记 { course[temp1]=i; //令temp1对应的值为i } //你这里的意思是如果课程之前有人标记过，就把他们凑到一起 Union(i,course[temp1]); } } for(int i=1; i<=n; i++) { isRoot[findFather(i)]++; //isRoot的值其实存放的是所有结点的父亲，然而数组中所有的人都是从1开始的 } int ans=0; for(int i=1; i<=n; i++) { if(isRoot[i]!=0) ans++; } sort(isRoot+1,isRoot+n,cmp); //所以说对应的排序应该是从1开始，而不是从数组的第1个位置开始 cout << ans << endl; for(int i=1; i<=ans; i++) { if(i!=1) cout << " "; cout << isRoot[i]; } return 0; }