用Leetcode 1971. Find if Path Exists in Graph為例子，想像一下我們建好圖後，先問節點0能不能走到節點３，BFS走完確定可以到後，這時又問節點1能不走到節點5，這樣每次問都要跑一遍BFS，有沒有什麼方法在建圖時順便記錄下這些節點有沒有連通？

並查集 Disjoint Set

Disjoint Set是一種資料結構，用來把元素分成若干個不重疊的集合，並且能快速判斷

• 兩個元素是否屬於同一集合

• 將兩個集合合併

所以上面的問題可以用Disjoint Set判斷他們倆元素是否同一集合就能解決。

優點：

1. 適合大量查詢：多次查詢不同節點是否同組。

2. 查詢快：透過演算法優化，幾乎 O(1)。

缺點：

1. 只能判斷連通性：只能回答是否在同一組

2. 不能給路徑或距離：不像 BFS/DFS 能告訴你完整路徑或最短距離。

Quick Find（查找快、合併慢）

適用：
查詢很多、合併少的情況。

做法
用一個陣列 id，id[i] 就是i 所屬集合的編號，一開始編號都是自己。

• find(x) = id[x] → 直接回傳所屬編號，O(1)

• union(a,b)：把所有a所屬集合的編號(id==id[a]) 的元素改成 id[b]代表a集合併到b集合 → O(N)（要掃整個陣列）

struct QuickFind {
    id: Vec<usize>,
}
impl QuickFind {
    fn new(n: usize) -> Self { Self { id: (0..n).collect() } }
    fn find(&self, x: usize) -> usize { self.id[x] }           // O(1)
    fn connected(&self, a: usize, b: usize) -> bool { self.find(a) == self.find(b) }
    fn union(&mut self, a: usize, b: usize) {                   // O(N)
        let (ra, rb) = (self.find(a), self.find(b));
        if ra == rb { return; }
        for v in self.id.iter_mut() {
            if *v == ra { *v = rb; }
        }
    }
}


fn main() {
    
    let mut uf = QuickFind::new(8);

    // 連接一些邊
    uf.union(0, 1); // 0 與 1 同集合
    uf.union(1, 2); // 0,1,2 同集合
    uf.union(3, 4); // 3 與 4 同集合
    uf.union(5, 6); // 5 與 6 同集合
    uf.union(6, 7); // 5,6,7 同集合
    uf.union(2, 5); // 把 {0,1,2} 與 {5,6,7} 合併為一大集合

    // 查詢幾組節點是否連通
    println!("connected(0, 7) = {}", uf.connected(0, 7)); // true
    println!("connected(3, 4) = {}", uf.connected(3, 4)); // true
    println!("connected(0, 3) = {}", uf.connected(0, 3)); // false
    println!("connected(4, 7) = {}", uf.connected(4, 7)); // false

    // 印出目前每個節點的代表值（Quick-Find 的 id 陣列）
    println!("id = {:?}", uf.id);
    // id = [7, 7, 7, 4, 4, 7, 7, 7]

}

Quick Union

適用：
合併很多、查詢少的情況。

做法：
每個節點只記錄一個 parent，集合用「樹」表示；root 的 parent 指向自己。

• find(x)：一路透過父節點(parent[x])往上查到 root(parent[x]==x) → O(樹高)，最壞 O(N)

• union(a,b)：把 a 的 root 指向 b 的 root → 近 O(1)只改原本a集合root的值，其他維持原狀

struct QuickUnion {
    parent: Vec<usize>,
}

impl QuickUnion {
    fn new(n: usize) -> Self {
        // 初始化：每個節點的父節點是自己（各自成為一棵樹的根）
        Self { parent: (0..n).collect() }
    }

    fn root(&self, mut x: usize) -> usize {
        // 追溯到根（樹高為時間複雜度）
        while self.parent[x] != x {
            x = self.parent[x];
        }
        x
    }

    fn connected(&self, a: usize, b: usize) -> bool {
        // 兩者根相同即連通
        self.root(a) == self.root(b)
    }

    fn union(&mut self, a: usize, b: usize) {
        // 合併兩棵樹：把 a 的根掛到 b 的根上（未做秩/大小優化，可能導致高樹）
        let (ra, rb) = (self.root(a), self.root(b));
        if ra != rb {
            self.parent[ra] = rb;
        }
    }
}

fn main() {
    // 建立 8 個節點：0..7
    let mut uf = QuickUnion::new(8);

    // 連接一些邊（示範）
    uf.union(0, 1); // 0 與 1 同集合
    uf.union(1, 2); // 0,1,2 同集合
    uf.union(3, 4); // 3 與 4 同集合
    uf.union(5, 6); // 5 與 6 同集合
    uf.union(6, 7); // 5,6,7 同集合
    uf.union(2, 5); // 把 {0,1,2} 與 {5,6,7} 合併為一大集合

    // 查詢幾組節點是否連通
    println!("connected(0, 7) = {}", uf.connected(0, 7)); // true
    println!("connected(3, 4) = {}", uf.connected(3, 4)); // true
    println!("connected(0, 3) = {}", uf.connected(0, 3)); // false
    println!("connected(4, 7) = {}", uf.connected(4, 7)); // false

    // 印出 parent 陣列（每個節點的父節點/根）
    println!("parent = {:?}", uf.parent);
    // parent = [1, 2, 7, 4, 4, 6, 7, 7]

}

Quick Union 優化

1. 在root找跟節點時，如果順便把parent更新成root，下一次再找有更新的節點集合時可以用O(1)的時間找到。

2. 在Union時比較rank，把rank小的合併到rank較大的root

為何需要rank小的集合掛到rank大的集合，主要是如果rank小掛到rank大可以在不增加樹高的情形下合併集合，搜尋維持在O(樹高)，無果你是rank大的集合掛到rank小的集合搜尋O(樹高+1)

struct QuickUnion {
    parent: Vec<usize>,
    rank: Vec<usize>,   
}

impl QuickUnion {
    fn new(n: usize) -> Self {
        // 初始化：每個節點的父節點是自己（各自成為一棵樹的根）
        Self { parent: (0..n).collect(), rank:vec![1;n] }
    }

    // 路徑壓縮的 find：遞迴找到根後，將沿途節點直接指向根
    fn find(&mut self, mut x: usize) -> usize {
        // 追溯到根（樹高為時間複雜度）
        if self.parent[x] != x {
            self.parent[x]=self.find(self.parent[x]);
        }
        self.parent[x]
    }

    fn connected(&mut self, a: usize, b: usize) -> bool {
        // 兩者根相同即連通
        self.find(a) == self.find(b)
    }

     // 將rank較小的根掛到rank較大的根；若rank相同，任選一方
    fn union(&mut self, a: usize, b: usize) {
        // 合併兩棵樹：把 a 的根掛到 b 的根上（未做秩/大小優化，可能導致高樹）
        let (ra, rb) = (self.find(a), self.find(b));
        // if ra != rb {
        //     self.parent[ra] = rb;
        // }
        if ra==rb {
            return
        }
        if self.rank[ra] < self.rank[rb] {
            self.parent[ra]=rb;
        } else if self.rank[ra] > self.rank[rb] {
            self.parent[rb]=ra;
        } else {
            self.parent[ra]=rb;
            self.rank[rb]+=1;
        }
    }
}

fn main() {
    // 建立 8 個節點：0..7
    let mut uf = QuickUnion::new(8);

    // 連接一些邊（示範）
    uf.union(0, 1); // 0 與 1 同集合
    uf.union(1, 2); // 0,1,2 同集合
    uf.union(3, 4); // 3 與 4 同集合
    uf.union(5, 6); // 5 與 6 同集合
    uf.union(6, 7); // 5,6,7 同集合
    
    println!("before union(2, 5) parent = {:?}", uf.parent);
    //before union(2, 5) parent = [1, 1, 1, 4, 4, 6, 6, 6]
    println!("before union(2, 5) rank = {:?}", uf.rank);
    //before union(2, 5) rank = [1, 2, 1, 1, 2, 1, 2, 1]
    
    uf.union(2, 5); // 把 {0,1,2} 與 {5,6,7} 合併為一大集合
    
    // 印出 parent 陣列（每個節點的父節點/根）
    println!("after union(2, 5) parent = {:?}", uf.parent);
    //after union(2, 5) parent = [1, 6, 1, 4, 4, 6, 6, 6]
    println!("after union(2, 5) rank = {:?}", uf.rank);
    //after union(2, 5) rank = [1, 2, 1, 1, 2, 1, 3, 1]
    
    // 查詢幾組節點是否連通
    println!("connected(0, 7) = {}", uf.connected(0, 7)); // true
    println!("after connected(0, 7) parent = {:?}", uf.parent);
    //after connected(0, 7) parent = [6, 6, 1, 4, 4, 6, 6, 6]，因為find更新了parent[0]
    println!("connected(3, 4) = {}", uf.connected(3, 4)); // true
    println!("connected(0, 3) = {}", uf.connected(0, 3)); // false
    println!("connected(4, 7) = {}", uf.connected(4, 7)); // false

}

Leetcode 1971 使用DSU

struct DSU {
    parent: Vec<usize>,
    rank: Vec<usize>,
}

impl DSU {
    fn new(n: usize) -> Self {
        DSU {
            parent: (0..n).collect(),
            rank: vec![0; n],
        }
    }

    fn find(&mut self, x: usize) -> usize {
        if self.parent[x] != x {
            let root = self.find(self.parent[x]);
            self.parent[x] = root; 
        }
        self.parent[x]
    }

    fn union(&mut self, a: usize, b: usize) {
        let mut ra = self.find(a);
        let mut rb = self.find(b);
        if ra == rb {
            return;
        }
        if self.rank[ra] < self.rank[rb] {
            self.parent[ra] = rb;
        } else if self.rank[ra] > self.rank[rb] {
            self.parent[rb] = ra;
        } else {
            self.parent[ra] = rb;
            self.rank[rb] += 1;
        }
    }
}

impl Solution {
    pub fn valid_path(n: i32, edges: Vec<Vec<i32>>, source: i32, destination: i32) -> bool {
        let mut dsu = DSU::new(n as usize);

        for edge in edges {
            dsu.union(edge[0] as usize, edge[1] as usize);
        }

        dsu.find(source as usize) == dsu.find(destination as usize)
    }
}

Day29 總結

1. DSU Quick Find & Quick Union介紹
2. DSU 優化