并查集

初始化

void init()
{
    for(int i = 1; i < N; i ++)
        fa[i] = i;
}

普通寻根

让子节点不断往上爬，当构建的图形成了一条链时，时间复杂度较高

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

void merge(int a, int b)
{
    int x, y;
    x = find(a), y = find(b);
    if(x == y)  return;
    fa[x] = y;
}

路径压缩

每次查找时都会将节点分开成一排，使得树高在2, 3之间，查找效率高

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

void merge(int a, int b)
{
    int x, y;
    x = find(a), y = find(b);
    if(x == y)  return;
    fa[x] = y;
}

按秩归并

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

void merge(int a, int b)
{
    int x, y;
    x = find(a), y = find(b);
    if(x == y)  return;

    if(ra[x] > ra[y]) swap(x, y);
    fa[x] = y;
    if(ra[x] == ra[y])  ra[y]++;
}

按大小归并

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

void merge(int a, int b)
{
    int x, y;
    x = find(a), y = find(b);
    if(x == y)  return;

    if(sz[x] > sz[y]) swap(x, y);
    fa[x] = y;
    sz[y] += sz[x];
}