并查集

用途

主要用于解决判断两结点是否能连通之类的问题。
　　
思想

建立并查集数组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，非常暴力。