并查集（杭电1232畅通工程、1213 How Many Tables）

并查集（杭电1232畅通工程、1213 How Many Tables）

从并查集的名字（Union/Find）来看，很容易理解并查集的算法。

举个栗子：

       黑白无常的boss是阎王，猴子的boss是唐僧，而唐僧的boss是如来。假设在黑白无常勾魂孙大圣的时候，他俩也喝多了，要拜把子当兄弟，于是乎“并”操作启动，在“并”的过程中，我们发现(查)猴子的最终boss是如来，黑白无常的最终boss是阎王，两个最终boss是不存在的，要知道一山还难容二公虎呢！

       那怎么办呢？打一架！赢了的就是老大，嘿嘿嘿~

      怎么用代码实现神仙打架呢？看“天命”——随机咯。比如我们指定以后阎王就是如来的boss了，如来肯定不愿意，但是天意如此，不可更改。

       而这个时候，我们还要求在猴子boss线上的所有人，以后都做阎王的小弟，而且是直属小弟。即唐僧、猴子、如来、黑白无常都是阎王的直属小弟了。

       当然，在一般的输入中，由于每步输入我们都有并查操作，所以不可能出现boss线上有三个人（如栗子中猴子->唐僧->如来）。

这里引入杭电1232来粗略讲解：

mix函数起到并的作用，Find函数用来查。

不难发现，并和查两个步骤并没有非常显著的分割线。

//1232杭电 #include<iostream>
#include<cstring>
using namespace std;
bool key[1010];//
int pre[1010];//
int Find(int x)
{int t=x;while(pre[t]!=t) t=pre[t];//查找boss元素，记为tint i=x,j;while(pre[i]!=t){j=pre[i];pre[i]=t;i=j;}                //将链接后整个祖孙线上的元素的直属boss全置为treturn t;
} 
void mix(int a,int b)
{int x=Find(a),y=Find(b);//查找bossif(x!=y) pre[y]=x;//如果两个人的boss不一样，则强制要求某一个boss做另一个的小弟
}
int main()
{int n;while(cin>>n&&n){for(int i=1;i<=n;i++) pre[i]=i;//每个人的boss是ta自己int m;cin>>m;for(int i=0;i<m;i++){int x,y;cin>>x>>y;mix(x,y);}                        //对每组输入进行“并”memset(key,0,sizeof(key));for(int i=1;i<=n;i++) key[Find(i)]=1;//标记boss！注意这里也有一个Find函数//for(int i=1;i<=n;i++) cout<<pre[i]<<",";cout<<endl;测试指令 int ans=0;for(int i=1;i<=n;i++) if(key[i]) ans++;//统计boss数cout<<ans-1<<endl;//减1原因很简单，两个点只要一条线连接}return  0;
} 

接下来是杭电的1213题（How Many Tables）：

这题我在网上找到一个更有意思的方法去标记。仔细研读了一番，发现自己还是想多用少经验不足。在此过程中，并没有将各个手下直接转为直属手下，而是依靠递归寻找它的boss。

话不多说，贴上代码：

#include<iostream>
using namespace std;
int pre[1010];
int find(int x)
{if(x==pre[x]) return x;else return find(pre[x]);//运用递归查找最终boss 
}
void mix(int a,int b)
{int x=find(a),y=find(b);if(x!=y) pre[x]=y;
}
int main()
{int t;cin>>t;while(t--){int n,m;cin>>n>>m;for(int i=1;i<=n;i++) pre[i]=i;while(m--){int a,b;cin>>a>>b;mix(a,b);}int ans=0;for(int i=1;i<=n;i++) if(pre[i]==i) ans++;//标记boss总数 //for(int i=1;i<=n;i++) cout<<pre[i]<<",";cout<<endl;测试指令 cout<<ans<<endl;}return 0;
}