并查集

路径压缩(图解):

#include<iostream>
#include<cstring>
#include<algorithm>
#define N 100010

using namespace std;

int n,m;
int p[N],d[N];

int find(int x)
{
    if(p[x] == x || p[p[x]] == p[x])    return p[x];
    int r = find(p[x]);
    d[x] += d[p[x]];
    p[x] = r;
    return r;
}

int main()
{
    scanf("%d%d",&n,&m);

    for(int i = 1;i <= n;i ++)   p[i] = i;

    while(m --)
    {
        int t,a,b;
        scanf("%d %d %d",&t,&a,&b);
        if(t == 1)
        {
            a = find(a),b = find(b);
            if(a != b)
            {
                d[a] -= d[b];   //这样才能保证a里面的子树节点值不变
                p[a] = b;
            }
        }
        if(t == 2)
        {
            a = find(a);
            d[a] += b;
        }
    }

    for(int i = 1;i <= n;i ++)
        if(i == find(i)) printf("%d ",d[i]);
        else    printf("%d ",d[i] + d[find(i)]);

    return 0;
}

路径压缩-优化法:

寻找祖先时采用递归，但是一旦元素一多起来，或退化成一条链，每次GetFather都将会使用O（n）的复杂度，这显然不是我们想要的。对此，我们必须要进行路径压缩，即我们找到最久远的祖先时“顺便”把它的子孙直接连接到它上面。这就是路径压缩了。使用路径压缩的代码如下，时间复杂度基
本可以认为是常数的。
路径压缩可以采用迭代和递归方式递归方式实现简单但是有些题目会爆栈的。
//递归形式的路径压缩

int getf(int v)
{
    if(v==f[v]) return v;
    return f[v]=getf(f[v]);
}

路径压缩具体写法:

#include<iostream>
#include<cstring>
#include<vector>
#define N 20010
#define M 220010
using namespace std;

int h[M],e[M],ne[M],idx;
int p[M+N];
int n,m;
int f[M];

void add(int a,int b)
{
    e[idx] = b,ne[idx] = h[a],h[a] = idx++;
}

int find(int x)
{
    if(p[x] != x)
    p[x] = find(p[x]);
    return p[x];
}

void dfs(int u,int fa)
{
    if(fa != -1)
    f[u] += f[fa];
    for(int i = h[u]; ~ i ;i = ne[i])
    {
        int j = e[i];
        dfs(j,u);
    }
}

int main()
{
    memset(h,-1,sizeof h);
    scanf("%d %d",&n,&m);
    int root = n+1;
    for(int i = 1;i < M;i ++)
    p[i] = i;
    while(m --)
    {
       int t,a,b;
       scanf("%d %d %d",&t,&a,&b);
       if(t == 1)
       {
            a = find(a),b = find(b);
            if(a != b)
            {
               add(root,a);
               add(root,b);
               p[a] = root;
               p[b] = root;
            }
            root ++;
       }
       else
       {
            a = find(a);
            f[a] += b;
       }
    }

    for(int i = n + 1;i < root;i ++)
        if(p[i] == i)

    dfs(i,-1);

    for(int i = 1;i <= n;i ++)
        printf("%d ",f[i]);

    cout<<endl;
    return 0;
}

按秩合并-优化法:

该方法使用秩来表示树高度的上界，在合并时，总是将具有较小秩的树根指向具有较大秩的树根。简单的说，就是总是将比较矮的树作为子树，添加到较高的树中。为了保存秩，需要额外使用一个与 uset 同长度的数组，并将所有元素都初始化为 0。这样找祖先会减少递归迭代的次数，最坏只有logN次。

void Merge(int x,int y)
{
    int t1=getf(x),t2=getf(y);
    if(t1==t2) return ;//已合并返回
    if(rnk[t1]>rnk[t2]) f[t2]=t1;  //把y的祖先t2和并到x的祖先t1上。因以t1为根的树更高
    else {
        f[t1]=t2;
        if(rnk[t1]==rnk[t2]) rnk[t2]++; //若两树一样高，那么合并后，高度加一。
    }
}