并查集板子

int f[maxn],h[maxn];//每个结点的父亲及树高

//初始化n个元素
void init(int n)
{
    for(int i = 0; i < n; ++i)
    {
        f[i] = i;
        h[i] = 0;
    }
}

//查询树的根
int find(int x)
{
    if(f[x] == x) return x;
    else return f[x] = find(f[x]);//路径压缩
}

//合并x和y所属的集合
void unite(int x, int y)
{
    x = find(x);
    y = find(y);
    if(x == y) return;
    //树高优化，由于find后已经路径压缩，所以x与y的高度差最多为1
    if(h[x] < h[y]) f[x] = y;//这里树高相差1（一个为1，一个为0），合并后x与y的高度都不变
    else
    {
        f[y] = x;
        if(h[x] == h[y]) h[x]++;//这里树高相等，合并后父亲高度加1
    }
}