基本概念

并查集能高效的查找兩個(gè)元素是否在一個(gè)集合，而且能高效的合并兩個(gè)集合。

• 使用樹結(jié)構(gòu)（Tree）來表示集合元素之間的關(guān)系
  每個(gè)元素是樹中的一個(gè)節(jié)點(diǎn)
  同一個(gè)集合的兩個(gè)元素在同一個(gè)樹上（有相同的root節(jié)點(diǎn)）
  不在同一集合的兩個(gè)元素在不同樹上（不同的root節(jié)點(diǎn)）
  初始狀態(tài)，每個(gè)節(jié)點(diǎn)為一棵樹
• 路徑壓縮算法
  用于find操作的時(shí)間優(yōu)化
  每個(gè)元素只關(guān)注其root節(jié)點(diǎn)
  每次查找時(shí)，將元素連接到root節(jié)點(diǎn)

實(shí)現(xiàn)

• 查找 (Find)
  時(shí)間復(fù)雜度為，幾乎是
  給一個(gè)元素，返回它的root節(jié)點(diǎn)
• 合并(Union)
  時(shí)間復(fù)雜度：
  把兩個(gè)元素所在的集合合并

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 相關(guān)練習(xí)

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