并查集 - UnionFind

基本概念

并查集能高效的查找两个元素是否在一个集合，而且能高效的合并两个集合。

• 使用树结构（Tree）来表示集合元素之间的关系
  每个元素是树中的一个节点
  同一个集合的两个元素在同一个树上（有相同的root节点）
  不在同一集合的两个元素在不同树上（不同的root节点）
  初始状态，每个节点为一棵树
• 路径压缩算法
  用于find操作的时间优化
  每个元素只关注其root节点
  每次查找时，将元素连接到root节点

实现

• 查找 (Find)
  时间复杂度为，几乎是
  给一个元素，返回它的root节点
• 合并(Union)
  时间复杂度：
  把两个元素所在的集合合并

class UnionFindSet {
    public int[] father;
    public UnionFindSet(int size) {
        father = new int[size];
        for(int i = 0; i < size; i++) {
            father[i] = i;
        }
    }
    public int find(int x) {
        if (father[x] == x) {
            return x;
        } else {
            return father[x] = find(father[x]);
        }
    }
    public void union(int a, int b) {
        int rootA = find(a);
        int rootB = find(b);
        if (rootA != rootB) {
            father[rootA] = rootB;
        }
    }
}

Lintcode 相关练习

Connecting Graph
Connecting Graph II
Connecting Graph III
Number of Islands
Number of Islands II
Graph Valid Tree
Minimum Spanning Tree
Driving problem