并查集

1. 定义

并查集是一种维护集合的数据结构，支持「合并」和「查找」两种操作，可用数组实现。

1.1. 数据结构

// father[i] 表示元素 i 的父亲节点
// 同一个并查集只有一个根节点
int father[N];

2. 基本操作

2.1. 初始化

for(int i=1;i<=N;i++){
    father[i]=i; // 令 father[i]=-1 也可
}

2.2. 查找

// 返回 x 所在并查集的根节点
int findFather(int x){
    while(x!=father[x]){
        x=father[x];
    }
    return x;
}

2.3. 合并

void Union(int a, int b){
    int faA=findFather(a);
    int faB=findFather(b);
    if(faA!=faB) father[faA]=faB;
}

3. 路径压缩

int findFather(int x){
    int a=x;
    while(x!father[x]){
        x=father[x];
    }
    // 把路径上经过的所有节点的父亲节点都改为根节点
    while(a!=father[a]){
        int z=a;
        a=father[a];
        father[z]=x;
    }
    return x;
}