并查集
并查集
先介绍一下什么是并查集。
并查集有无权并查集和有权并查集两种。并查集的作用是将有关联的元素合并为一个集合的东东，是图这一结构中常用到的。假设，以亲属关系为例，你亲戚的亲戚也算是和你有点关系，所以你们就在一个集合当中。因此，在图中，并查集可以很方便得知道两点是否在一个集合中（即两点之间是否连通）。同时，并查集也能判定此图中是否存在环路。
首先来看下无权并查集：
我将其做成了类的形式
struct DisJointSet{
vector<int> father,rank;
DisJointSet(int n);//初始化
int findRoot(int x);//寻找根节点，核心操作，注意和父亲结点不同
void merge(int x,int y);//将两个有联系的元素进行合并
bool same(int x,int y);//判定是否在同一个集合当中
};
无权并查集中主要有两组元素------父亲节点，节点高度（也可以说是树高）。
对于初始化：所有元素均是独立的，因此他们的父亲节点即为他们自己，每个节点的树高也因此为0；
DisJointSet::DisJointSet(int n):father(n+1),rank(n+1){//此处利用的vector的构造函数
for(int i=0;i<n+1;i++){
father[i]=i;
rank[i]=0; //record the height
}
}
对于查找根节点（注：不是父亲节点，稍后会介绍原因）的操作，只需利用递归即可。
int DisJointSet::findRoot(int x){
return father[x]==x?x:findRoot(father[x]);//可以改进
}
先讲same函数：如果他们的根节点相同，则他们在同一个集合中。因此，代码很容易得出。
bool DisJointSet::same(int x,int y){
return findFather(x)==findFather(y);
}
最重要的操作：合并。如图，最开始事有10个元素。每个结点的父亲结点都是他们本身，每个元素的高度为0。并且，每个元素所处集合的根节点也为他本身。此时，图上的根节点有：0，1，2，3，4，5，6，7，8，9.
我先依次合并（0，1），（2，3），（4，5），（8，9）。
我们可以清楚得看到，我这里是将前一个元素连接到后一个元素上（你也可以自定义，但最好统一，不然结点高度的变化会很复杂），此时，图中的根节点有：1，3，5，7，8，9；部分节点的树高也发生了变化。
接下来，我们来依次合并（0，2），（5，6）。
我们发现，我们是将（1，3）连接，（5，7）连接，即对根结点进行合并，并跟新根结点的高度。到此为止，应该对并查集有了一个很好的认识，那么，最后，我们再将（3，7，8，9）依次合并。得到最后的图形。
接下来给出代码：
void DisJointSet::merge(int x,int y){
int a=findRoot(x),b=findFather(y);
if(a!=b){//如果两个点已经在同一集合中，则不需要合并
if(_rank[a]>_rank[b]){//我们规定，短链接到长链上。
father[b]=a;
}else{
father[a]=b;
if(_rank[a]==_rank[b])//只有两条链长度相等时，才需要更新结点高度
_rank[b]++;
}
}
}
我们看可以发现，对于每次操作，都需要访问根节点。但是father记录的只是其父亲结点，并非根节点，那么我们是否需要再加一个root数组来存储根节点的信息呢？其实，完全不需要，我们只需对findRoot函数做出如下改进即可：
int findRoot(int x){
return father[x]=father[x]==x?x:findRoot(father[x]);
//利用每次的查找来更新父亲结点，使得进行过findRoot操作的结点的父亲结点最终记录的就是根节点信息
//此方法就是压缩
}
给出完整代码：
struct DisJointSet{
vector<int> father,_rank;
DisJointSet(int n):father(n+1),_rank(n+1){
for(int i=0;i<n+1;i++){
father[i]=i;
_rank[i]=0; //record the height
}
}
int findRoot(int x){
return father[x]=father[x]==x?x:findRoot(father[x]);
}
void merge(int x,int y){
int a=findFather(x),b=findFather(y);
if(a!=b){
if(_rank[a]>_rank[b]){
father[b]=a;
}else{
father[a]=b;
if(_rank[a]==_rank[b])
_rank[b]++;
}
}
}
bool same(int x,int y){
return findFather(x)==findFather(y);
}
};
无权并查集再这里就介绍完了。再补充一条：如何利用并查集来判环。如果再两个结点合并前，这两个结点已经属于一个集合（利用same函数），那么这个图中就存在环路。由于证明过于简单，这里就不再说了。
有权并查集：
有权无权在并查集的代码结构上是没有任何区别的，但多了另一重要元素------权值，因此在合并时需要将他们之间的差值输入。本文用val数组来存储以及对权值的更新操作（在merge和findRoot中完成）。
给出一个例子：某次考试a地到b地需要10分钟，b地到c地需要10分钟，因此a地到c地就需要20分钟（假设就只有这一条路从a地到c地）。我们规定（也可以自行规定）：此时a的权值为0，b的权值为10。c的权值为20（即每个结点的权值其实是他到根节点的开销）。注意：这是有向的。
初始化操作：只是在无权图的基础上多了一步将val[i]初始化成0。
find操作：利用递归查找父亲并更新结点权值（看了代码自然就明白了，先别急）。
合并操作：如图，这里有4个结点，假设merge（0，1，val1），merge（2，3，val2），则val[0]=val1，val[1]=0，val[2]=val2，val[3]=0（显然）。
接下来我merge（0，2，s）。我们发现有两种可能：1.将1并入3所在的集合；2.将3并入1所在的集合。给出下图，方便推导。
第一种情况：
0+val1=1,val1=val[0]
0 + s =2
2+val2=3,val2=val[2]
所以val[1]=3-1=val[2]-val[1]+val[2–>0]=val[2]-val[1]-s
第二种情况(同理)：val[3]=s+val[1]-val[2]
其实对于任何merge(x,y,val)都满足如上两种情况之一，这里就不给出证明了。直接给出代码。
int f[maxn],r[maxn],val[maxn];
void init(int n){//初始化
for(int i=0;i<n;i++)
f[i]=i,r[i]=0,val[i]=0;
}
int find(int x){//查找根节点
if(x==f[x])
return x;
else{
int t=f[x];
f[x]=find(f[x]);//压缩
val[x]+=val[t];//更新权值
return f[x];
}
}
void merge(int x,int y,int s){
int fx=find(x);
int fy=find(y);
if(fx!=fy){
if(r[fx]<r[fy]){
f[fx]=fy;
val[fx]=s-val[x]+val[y]; //第二种情况
}
else{
f[fy]=fx;
val[fy]=val[x]-val[y]-s;//第一种情况
if(r[fx]==r[fy])
r[fx]++;
}
}
}
所以，val[x]-val[y]就是x到y的其中一种开销了。（对于无环图就是x到y的开销）
这里再附上一个裸题：http://hihocoder.com/problemset/problem/1515
终于写完了啊！！！