UVA 10608 Friends 并查集 - c++编程基础

并查集水题
有n个人，m队朋友，朋友的朋友，也是朋友，A与B是朋友，B与C是朋友，那么A与C也是朋友，即A，B，C在同一个并查集里，合并即可；

最后会有几个“朋友圈子”，求最大的朋友圈的人数。

#include
  
   
#include
   
     #include
    
      #include
     
       using namespace std; int r[30005]; int x[30010]; int init(int n)/// 初始化 { for(int i=1;i<=n;i++) r[i]=i; } int find_(int x) ///寻找根 { int n=x,t; while(r[x]!=x) x=r[x]; while(n!=r[n]){ /// 路径压缩 路过的点全部指向根 t=r[n]; r[n]=x; n=r[n]; } return x; } int cmp(int x,int y) { return x>y; } int main() { int n,m,i,T,a,b; scanf("%d",&T); while(T--){ scanf("%d%d",&n,&m); init(n); while(m--){ scanf("%d%d",&a,&b); int aa=find_(a); int bb=find_(b); if(aa!=bb)/// 合并 r[aa]=bb; } memset(x,0,sizeof(x)); for(i=1;i<=n;i++) x[find_(i)]++;/// 哈希，在一个朋友圈里，则find_(i)相同， 累加 int ans=0; for(i=1;i<=n;i++) if(ans