并查集 §

用途 §

处理不相交集的合并与查询问题

经典题目：leetcode200 岛屿问题

单个元素的数据结构 §

• Parent：元素的父节点
• Rank：元素所在的层次，即以该元素为根节点的树的深度 - 1，用于合并时选择根节点
• Data：集合代表的数据

算法步骤 §

初始化 §

初始化时每个元素都被视为是一棵独立的树：

• 将所有元素的父节点 parent 设置为元素本身 (便于判断元素是否为根节点)
• 将所有元素的层次 rank 设置为 0。

查找 §

查找元素的 parent，直至寻找到所在树的根节点

// 查找根节点 
public int find(int x) { 
    while(x != parent[x]) { 
        // 路径压缩（隔代压缩） 
        parent[x] = parent[parent[x]]; 
        x = parent[x]; 
    } 
    return x; 
}

为了加快查找速度，可以进行路径压缩。可以如上面代码那样，通过隔代压缩缩短搜寻路径；也可以在查找完成后，将所有途经节点的父节点都设置为这棵树的根节点。

合并 §

将 a 所在树与 b 所有树合并，首先找到 a 所在树和 b 所在树的根节点 roota 和 rootb。然后将 roota 的 parent 指向 b，或 rootb 的 parent 指向 a。为了防止树退化，在选择是 a 指向 b 还是 b 指向 a 的时候，根据两者的 rank 判断，使合成后的树的左右子树的层级尽量相同。

// 合并  
public void union(int x, int y) {  
    // 找到根节点
    int rootX = find(x);  
    int rootY = find(y);  
    if(rootX == rootY) {  
        return;  
    } 
    // 合并时使左右子树的深度尽量一致  
    if(rank[rootX] < rank[rootY]) {  
        parent[rootX] = rootY;  
    } else {  
        parent[rootY] = rootX;  
        if(rank[rootX] == rank[rootY]) {  
            rank[rootX]++;  
        } 
    }  
}

统计集合数量 §

遍历所有元素，查看有多少个元素的 parent 为它本身。