并查集-UnionFind

发表于 | 分类于
字数统计: 316

基本概念

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

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

实现

  • 查找 (Find)
    时间复杂度为$O(log*n)$，几乎是$O(1)$
    给一个元素，返回它的root节点
  • 合并(Union)
    时间复杂度：$O(1)$
    把两个元素所在的集合合并
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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