1 #include <iostream> 2 #include <fstream> 3 #include <cstring> 4 #include <vector> 5 #include <queue> 6 #include <stack> 7 #include <algorithm> 8 #include <cmath> 9 10 using namespace std;11 12 #define loop(i,n) for(int i=0;i<(n);i++)13 #define loop2(i,n) for(int i=1;i<=(n);i++)14 15 const int maxn=1000;16 int inf=99999999;17 18 int f[maxn];19 int n,m,k,sum=0;20 //这是初始化，非常重要，数组里面存的是自己数组下标的编号就好了21 void init()22 {23   for(int i=1;i<=n;i++)24     f[i]=i;25 }26 //这是找爹的递归函数，不停地去找爹，直到找到祖宗为止，其实就是去找犯罪团伙的最高领导人，擒贼先擒王原则27 int getf(int v)28 {29   if(f[v]==v)30     return v;31   else32   { //路径压缩，每次在函数返回的时候，顺带把路上遇到的人的BOSS改为最后找到的祖宗编号，也就是犯罪团伙的最高领导人编号33     f[v]=getf(f[v]);34     return f[v];35   }36 }37 //这里是合并两子集的函数38 void merge(int v,int u)39 {40   int t1,t2;41   t1=getf(v);42   t2=getf(u);43   if(t1!=t2) //判断两个结点是否在同一个集合中，即是否为同一个祖先44     f[t2]=t1; //"靠左“原则，左边变成右边的BOSS。即把右边的集合，作为左边集合的子集合，经过路径压缩以后，将f[u]的根的值也赋值为v的祖先f[t1]45 }46 47 void test()48 {   49   freopen("unionn.in","r",stdin);  50   //freopen("unionn.out","w",stdout); 51   int x,y;52   cin>>n>>m;53   init();54   for(int i=1;i<=m;i++)55   {56     cin>>x>>y;57     merge(x,y); //开始合并犯罪团伙   58   }59 60   for(int i=1;i<=n;i++)  //最后扫描有多少个独立的犯罪团伙61   {62     cout<<f[i]<<" ";63     if(f[i]==i)64       sum++;65   }66   cout<<endl;67   cout<<sum<<endl; 68 }69 70 int main () 71 {        72     test();        73     return 0;74 }

10 91 23 45 24 62 68 79 71 62 4