【PAT甲级】1107 Social Clusters (30分)（非递归并查集）

题意：

输入一个正整数N（<=1000），表示人数，接着输入N行每行包括一个他的爱好数量：和爱好的序号。拥有相同爱好的人们可以默认他们在同一个俱乐部，输出俱乐部的数量并从大到小输出俱乐部的人数（不同俱乐部的两个人的爱好一定不相同）。

AAAAAccepted code：

 #define HAVE_STRUCT_TIMESPEC

 #include<bits/stdc++.h>

 using namespace std;

 vector<int>v[],st;

 int fa[];

 int a[];

 int find_(int x){

     int k,j,r;

     r=x;

     while(r!=fa[r])

         r=fa[r];

     k=x;

     while(k!=r){

         j=fa[k];

         fa[k]=r;

         k=j;

     }

     return r;

 }

 int main(){

     ios::sync_with_stdio(false);

     cin.tie(NULL);

     cout.tie(NULL);

     int n;

     cin>>n;

     st.resize(n+);

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

         fa[i]=i;

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

         int x;

         cin>>x;

         cin.ignore();

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

             int y;

             cin>>y;

             v[i].push_back(y);

         }

     }

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

         for(auto it:v[i])

             if(!a[it])

                 a[it]=i;

             else{

                 int x=find_(i);

                 int y=find_(a[it]);

                 if(x!=y)

                     fa[x]=y;

             }

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

         ++st[find_(i)];

     int cnt=;

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

         if(st[i])

             ++cnt;

     cout<<cnt<<"\n";

     sort(st.rbegin(),st.rend());

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

         cout<<st[i];

         if(i<cnt-)

             cout<<" ";

     }

     return ;

 }