PTA朋友圈（并查集的应用）
7-8 朋友圈 (25 分)
某学校有N个学生，形成M个俱乐部。每个俱乐部里的学生有着一定相似的兴趣爱好，形成一个朋友圈。一个学生可以同时属于若干个不同的俱乐部。根据“我的朋友的朋友也是我的朋友”这个推论可以得出，如果A和B是朋友，且B和C是朋友，则A和C也是朋友。请编写程序计算最大朋友圈中有多少人。
输入格式:
输入的第一行包含两个正整数N（≤30000）和M（≤1000），分别代表学校的学生总数和俱乐部的个数。后面的M行每行按以下格式给出1个俱乐部的信息，其中学生从1~N编号：
第i个俱乐部的人数Mi（空格）学生1（空格）学生2 … 学生Mi
输出格式:
输出给出一个整数，表示在最大朋友圈中有多少人。
输入样例:
7 43 1 2 32 1 43 5 6 71 6输出样例:
4只过了测试点1的代码：
#includeusing namespace std;int a[30001];int root(int x)//求出所在的根{ return x==a[x]? x:a[x]=root(a[x]);}int rt(int x)//用于求并查集建立起来的树中该节点的祖先数{int sum=0;while(a[x]!=x){x=a[x];sum++;}return sum+2;}void un(int x,int y)//合并两颗树{int xx=root(x);int yy=root(y);if(xx!=yy)a[xx]=yy;}int main(){int n,m;cin>>n>>m;for(int i=1;i<=n;i++)//初始化a[i]=i;for(int i=1;i>k;int x;cin>>x;while(--k){int xx;cin>>xx;un(a[x],a[xx]);x=xx;}}int ans=0;for(int i=1;i<=n;i++){int sum=rt(a[i]);ans=max(sum,ans);}cout<<ans; return 0;}
过了测试点1、2的代码：
#includeusing namespace std;int a[30001];int root(int x){ return x==a[x]? x:a[x]=root(a[x]);}int rt(int x){int sum=0;while(a[x]!=x){x=a[x];sum++;}return sum+1;//原来是sum+2现在改成sum+1}void un(int x,int y){int xx=root(x);int yy=root(y);if(xx!=yy)a[xx]=yy;}int main(){int n,m;cin>>n>>m;for(int i=1;i<=n;i++)a[i]=i;for(int i=1;i>k;int x;cin>>x;while(--k){int xx;cin>>xx;un(a[x],a[xx]);x=xx;}}int ans=0;for(int i=1;i<=n;i++){int sum=rt(i);//原来是rt(a[i])现在改为rt(i)ans=max(sum,ans);}cout<<ans; return 0;}
AC代码：
#includeusing namespace std;int a[30001];int root(int x){ return x==a[x]? x:a[x]=root(a[x]);}void un(int x,int y){int xx=root(x);int yy=root(y);if(xx!=yy)a[xx]=yy;}int main(){int n,m;cin>>n>>m;for(int i=1;i<=n;i++)a[i]=i;for(int i=1;i>k;int x;cin>>x;while(--k){int xx;cin>>xx;un(a[x],a[xx]);x=xx;}}map mp;//采用map效率高 for(int i=1; imax) max = x.second;//不断更新求出最大朋友圈人数 cout << max; return 0;}
不用map但用路径压缩优化并查集后的另一种AC代码 ：
#includeusing namespace std;int a[30001];int mp[30001];int root(int x){ int r=x; while(a[r]!=r) r=a[r]; int i=x,j; while(i!=r)//路径压缩算法（对于每个结点，一旦向上走到了一次根结点，就把这个点到父亲的边改为直接连向根，这样再次查询这些结点时，就能很快知道根） { j=a[i];//记录x的前导结点 a[i]=r;//将i的前导结点设置为r根节点 i=j; } return r;}void un(int x,int y){int xx=root(x);int yy=root(y);if(xx!=yy)a[xx]=yy;}int main(){int n,m;cin>>n>>m;for(int i=1;i<=n;i++)a[i]=i;for(int i=1;i>k;int x;cin>>x;while(--k){int xx;cin>>xx;un(a[x],a[xx]);x=xx;}}for(int i=1; i<=n; i++) mp[root(i)]++; int max = 0; for(int i=1;imax) max=mp[i];} cout << max; return 0;}如果把map换成数组又不用路径压缩的话，会导致最后一个测试点运行超时！
再来一道类似的并查集题目练练吧！
#includeusing namespace std;int a[1001];int mp[1001],man[1001];//man[]为第i个人对应一个爱好编号（对应的爱好编号没有特别限制，也可以用第一个爱好编号，这里接下来用的是最后一个爱好编号）int root(int x){while(a[x]!=x)x=a[x];return x;}void un(int x,int y){int xx=root(x);int yy=root(y);if(xx!=yy)a[xx]=yy;}int main(){int n;cin>>n;for(int i=1;i<=1000;i++)a[i]=i;for(int i=1;i>k>>c;int x;cin>>x;while(--k){int xx;cin>>xx;un(x,xx);x=xx;}man[i]=x;//对应爱好编号}for(int i=1;i<=n;i++)mp[root(man[i])]++;int cnt=0;vectorv;for(int i=1;i<=1000;i++){if(mp[i]){cnt++;v.push_back(mp[i]);}}sort(v.begin(),v.end(),greater());cout<<cnt<<endl;bool f=false;for(auto i:v){if(f)cout<<" ";cout<<i;f=true;} return 0;}
本萌新刚接触并查集，有很多地方理解不到位或者错误，各位大佬可以踊跃指出，感激不 尽！！！（同时这也是我第一次尝试写博客(灬°ω°灬)）