用途
主要用于解决判断两结点是否能连通之类的问题。
思想
建立并查集数组set[]，初始化全部置-1。set[b]=a代表结点b的父结点为a。判断两结点是否连通，只要依次找到两结点的根结点并判断是否相同即可。若不同，将一结点的根节点连接作为另一节点根节点的子树，即可完成连通操作。
/*寻根*/
int findRoot(int x)
{
while(set[x]!=-1)
x=set[x];
return x;
}
/*连通操作*/
void Union(int a,int b)
{
set[findRoot(b)]=findRoot(a);
}
注意
用以上方法操作时，一旦数据过多，往往会造成运行超时的结果，原因在于并查集树过高，搜索根节点时间长。下面提供两种解决思路：
1.路径压缩
变更set[i]值的含义，将set[i]直接指向包含结点i的树的根节点，使每次查找根节点所需时间大大减少。具体做法为：每一次寻根的时候，变更set[i]值为根节点。经过路径压缩后效率可以达到O(N)。
/*路径压缩*/
int findRoot(int x)
{
/*注意x即为根节点的情况，此时直接返回x即可*/
if(set[x]==-1)
return x;
else
{
int temp=x; //先将x的值保存下来
while(set[x]!=-1)
x=set[x];
set[temp]=x; //更新set[]
return x;
}
}
2.按秩归并
压缩路径存在的一个问题是会破坏树的形状，这是可以考虑使用按秩归并的方法。
对于两颗高度不一的树，若将高树并到矮树上，则得到的树高度为原高树高度加一，为了不使树一直增高，我们采取的做法是每一次合并都将矮树合并到高树上（通过根节点的值来记录树高，即set[root]=-树高）。当然也可以从树的规模入手，将小树归并到大树上。
最坏情况下树高O(logN)，按秩归并的复杂度可以低至O(NlogN)。
/*比高度，set[root]存储高度*/
void Union(int a,int b)
{
int aRoot=findRoot(a);
int bRoot=findRoot(b);
if(set[aRoot]<set[bRoot]) //若a为高树
set[bRoot]=aRoot;
else
{
if(set[aRoot]==set[bRoot]) //若树高相等
--set[bRoot]; //合并后树高要加一
set[aRoot]=bRoot;
}
}
/*比规模，set[root]存储规模*/
void Union(int a,int b)
{
int aRoot=findRoot(a);
int bRoot=findRoot(b);
if(set[aRoot]<set[bRoot]) //a规模大于b
{
set[aRoot]+=set[bRoot];//注意规模要合并
set[bRoot]=aRoot;
}
else
{
set[bRoot]+=set[aRoot];
set[aRoot]=bRoot;
}
}
3.以上两种方法相结合，可以实现-1s，非常暴力。
