Chương 24 - Union Find (Disjoint Set Union)

Union Find (DSU) là cấu trúc dữ liệu cho 2 thao tác trên các tập rời: (i) find(x) - root của tập chứa x, (ii) union(x, y) - gộp 2 tập. Với path compression + union by rank/size, mỗi op gần như O(1) (chính xác O(α(n)) với α là hàm Ackermann ngược).

Mục tiêu chương

Sau chương này, bạn sẽ:

  • DSU 2 op cốt lõi: find (path compression) và union (by rank/size).
  • Mỗi op gần O(1) (chính xác O(α(n))).
  • Pattern: online thêm cạnh, đếm component, detect cycle undirected.
  • Offline DSU: sort cạnh theo trọng số → query threshold.

Khi nào dùng pattern này?

  • Đếm / kiểm tra connected components trong undirected graph khi cạnh thêm dần (không thể BFS lại từ đầu mỗi lần).
  • Bài “có chu trình không” trong undirected graph (cạnh nối 2 đỉnh cùng root).
  • Kruskal MST (Chương 33).
  • Bài “offline” mà các query có thể sắp xếp (LC 1697, 1632).

Template code 

class DSU:
    def __init__(self, n: int):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.size = [1] * n
        self.components = n

    def find(self, x: int) -> int:
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]   # path compression
            x = self.parent[x]
        return x

    def union(self, x: int, y: int) -> bool:
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return False              # đã cùng tập
        # Union by rank - đính cây thấp dưới cây cao.
        if self.rank[rx] < self.rank[ry]:
            rx, ry = ry, rx
        self.parent[ry] = rx
        self.size[rx] += self.size[ry]
        if self.rank[rx] == self.rank[ry]:
            self.rank[rx] += 1
        self.components -= 1
        return True

    def connected(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)

Bài tự luyện cuối chương

  • LC 261 - Graph Valid Tree
  • LC 1319 - Number of Operations to Make Network Connected
  • LC 1631 - Path With Minimum Effort
  • LC 1697 - Checking Existence of Edge Length Limited Paths

24.1 Number of Provinces (LC 547)

Đề bài

Có n thành phố và ma trận isConnected[i][j] = 1 nếu i, j nối trực tiếp. Province là tập thành phố liên thông. Đếm số province.

Ví dụ 

Input:  isConnected=[[1,1,0],[1,1,0],[0,0,1]]
Output: 2

Ràng buộc

  • 1 <= n <= 200
  • isConnected[i][i] = 1

Clarifying questions

  • isConnected[i][i] = 0 hay 1? → Theo LC: = 1 (tự đến mình).
  • Multi-edge? → Không vấn đề với DSU.

Hướng tiếp cận

DSU: union các cặp có cạnh, đếm components. Hoặc DFS/BFS

  • đơn giản hơn.

Code Python 3 

from typing import List

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        n = len(isConnected)
        dsu = DSU(n)
        for i in range(n):
            for j in range(i + 1, n):
                if isConnected[i][j]:
                    dsu.union(i, j)
        return dsu.components

Phân tích độ phức tạp

  • Thời gian: O(n² · α(n)). Bộ nhớ: O(n).

Bình luận

  • Khi nào DSU tốt hơn DFS? Khi có nhiều query “u, v cùng province?” sau khi đã build - DSU O(α) per query.

Bài tự luyện liên quan

  • LC 200 - Number of Islands.

24.2 Redundant Connection (LC 684)

Đề bài

Input: edges: List[List[int]] - mảng cạnh [u, v] của graph vô hướng. Graph này được tạo từ 1 tree (n đỉnh, n-1 cạnh) sau đó thêm 1 cạnh thừa làm xuất hiện chu trình. Tìm cạnh thừa cuối cùng trong input có thể xoá để còn lại là tree.

Ví dụ 

Input:  edges=[[1,2],[1,3],[2,3]]
Output: [2,3]

Ràng buộc

  • n == edges.length
  • 3 <= n <= 1000

Clarifying questions

  • Có thể có nhiều edge thừa? → Đề bảo đảm đúng 1 cycle.

Hướng tiếp cận

DSU union từng cạnh. Cạnh đầu tiên mà find(u) == find(v) đã → đó là cạnh tạo chu trình → return.

Code Python 3 

from typing import List

class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        n = len(edges)
        dsu = DSU(n + 1)
        for u, v in edges:
            if not dsu.union(u, v):
                return [u, v]
        return []

Phân tích độ phức tạp

  • Thời gian: O(E · α(V)).
  • Bộ nhớ: O(V).

Bình luận

  • Pattern “cạnh tạo cycle” là use case kinh điển của DSU.
  • Follow-up LC 685 - Redundant Connection II: directed graph, phức tạp hơn (xét cả indegree).

Bài tự luyện liên quan

  • LC 685 - Redundant Connection II.
  • LC 261 - Graph Valid Tree.

24.3 Accounts Merge (LC 721)

Đề bài

Cho mảng accounts, mỗi cái = [name, email1, email2, ...]. 2 account thuộc cùng người ↔︎ chia sẻ ít nhất 1 email. Gộp các account cùng người thành 1, output email sorted lex.

Ví dụ 

Input:  accounts=[["John","a@x","b@x"],["John","b@x","c@x"],["Mary","d@x"]]
Output: [["John","a@x","b@x","c@x"],["Mary","d@x"]]

Ràng buộc

  • 1 <= len(accounts) <= 1000
  • 2 <= len(accounts[i]) <= 10

Clarifying questions

  • Một account có duplicate email? → Có thể; DSU xử lý tự nhiên.

Hướng tiếp cận

  • Mỗi email là 1 node trong DSU.
  • Với mỗi account, union email[0] với các email khác.
  • Map mỗi email → name (để lấy tên cuối).
  • Group emails theo root → mỗi nhóm = 1 account hợp nhất.

Code Python 3 

from collections import defaultdict
from typing import List

class Solution:
    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
        dsu_parent: dict[str, str] = {}
        email_to_name: dict[str, str] = {}

        def find(x: str) -> str:
            if dsu_parent.setdefault(x, x) != x:
                dsu_parent[x] = find(dsu_parent[x])
            return dsu_parent[x]

        def union(x: str, y: str) -> None:
            dsu_parent[find(x)] = find(y)

        for acc in accounts:
            name, emails = acc[0], acc[1:]
            for e in emails:
                email_to_name[e] = name
                union(emails[0], e)

        groups: dict[str, list[str]] = defaultdict(list)
        for e in email_to_name:
            groups[find(e)].append(e)

        return [[email_to_name[g[0]]] + sorted(g) for g in groups.values()]

Phân tích độ phức tạp

  • Thời gian: O(N · L · α(N · L) + N · L log(L)) cho sort.
  • Bộ nhớ: O(N · L).

Bình luận

  • Tinh thần: DSU trên email thay vì trên account index - đơn giản hơn vì shared email tự nhiên tạo union.

Bài tự luyện liên quan

  • LC 952 - Largest Component Size by Common Factor (Chương 20.5).

24.4 Number of Islands II (LC 305)

Đề bài

Cho grid m × n ban đầu toàn nước. Cho mảng positions[i] = [r, c] - biến mỗi ô thành đất theo thứ tự. Sau mỗi thêm, trả về số đảo hiện tại.

Ví dụ 

Input:  m = 3, n = 3
        positions = [[0,0], [0,1], [1,2], [2,1]]

Output: [1, 1, 2, 3]

Trace từng bước:

  Sau [0,0]:  [1, 0, 0]     → 1 đảo
              [0, 0, 0]
              [0, 0, 0]

  Sau [0,1]:  [1, 1, 0]     → 1 đảo  (nối với (0,0))
              [0, 0, 0]
              [0, 0, 0]

  Sau [1,2]:  [1, 1, 0]     → 2 đảo
              [0, 0, 1]
              [0, 0, 0]

  Sau [2,1]:  [1, 1, 0]     → 3 đảo
              [0, 0, 1]
              [0, 1, 0]

Ràng buộc

  • 1 <= m, n <= 10^4
  • 1 <= len(positions) <= 10^4

Clarifying questions

  • Vị trí trùng (cùng position được thêm 2 lần)? → Skip lần thứ 2.

Hướng tiếp cận

DSU online. Mỗi position: - Mark ô là đất, components += 1. - Với mỗi hàng xóm 4 hướng đã là đất, union → nếu union thành công, components -= 1. - Push components vào kết quả.

Code Python 3 

from typing import List

class Solution:
    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:
        parent = [-1] * (m * n)         # -1 = nước
        components = 0
        DIRS = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        result: list[int] = []

        def find(x: int) -> int:
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x

        def union(x: int, y: int) -> bool:
            rx, ry = find(x), find(y)
            if rx == ry: return False
            parent[rx] = ry
            return True

        for r, c in positions:
            idx = r * n + c
            if parent[idx] != -1:
                result.append(components)
                continue
            parent[idx] = idx
            components += 1
            for dr, dc in DIRS:
                nr, nc = r + dr, c + dc
                if 0 <= nr < m and 0 <= nc < n:
                    nidx = nr * n + nc
                    if parent[nidx] != -1 and union(idx, nidx):
                        components -= 1
            result.append(components)
        return result

Phân tích độ phức tạp

  • Thời gian: O(K · α(mn)) với K = số position.
  • Bộ nhớ: O(mn).

Bình luận

  • Bài này là ví dụ tiêu biểu của Union Find - minh hoạ rõ thế mạnh của DSU ở pattern “online merging” (thêm node và gộp component theo thời gian).
  • Bẫy: position trùng → check parent[idx] != -1 để skip.

Bài tự luyện liên quan

  • LC 200 - Number of Islands.

24.5 Satisfiability of Equality Equations (LC 990)

Đề bài

Cho mảng equations dạng "a==b" hoặc "a!=b". Trả về True nếu có thể gán giá trị cho biến thoả tất cả equations.

Ví dụ 

Input:  ["a==b","b!=a"]
Output: False

Ràng buộc

  • 1 <= len(equations) <= 500
  • equations[i] có dạng “a==b” hoặc “a!=b”

Clarifying questions

  • Equation với cùng biến (a == a)? → Hiển nhiên True; code vẫn xử lý đúng.

Hướng tiếp cận

2 lượt: 1. Union các == equation. 2. Kiểm tra != equation: nếu 2 biến cùng root → mâu thuẫn.

Code Python 3 

from typing import List

class Solution:
    def equationsPossible(self, equations: List[str]) -> bool:
        parent = list(range(26))

        def find(x):
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x

        for eq in equations:
            if eq[1] == '=':
                parent[find(ord(eq[0]) - 97)] = find(ord(eq[3]) - 97)
        for eq in equations:
            if eq[1] == '!':
                if find(ord(eq[0]) - 97) == find(ord(eq[3]) - 97):
                    return False
        return True

Phân tích độ phức tạp

  • Thời gian: O((E + Q) · α(26)).
  • Bộ nhớ: O(26).

Bình luận

  • Pattern “union trước, check sau” - phổ biến trong DSU.

Bài tự luyện liên quan

  • LC 947 - Most Stones Removed with Same Row or Column.

24.6 Swim in Rising Water (LC 778)

Đề bài

Ma trận grid[i][j] = “elevation” tại ô (i, j). Tại thời điểm t, ô có elevation ≤ t có nước phủ đủ để bơi vào. Bắt đầu (0, 0), mục tiêu (n-1, n-1). Tìm t nhỏ nhất.

Ví dụ 

Input:  grid=[[0,1,2,3,4],[24,23,22,21,5],[12,13,14,15,16],[11,17,18,19,20],[10,9,8,7,6]]
Output: 16

Ràng buộc

  • n == grid.length
  • 1 <= n <= 50

Clarifying questions

  • Grid 1×1? → Trả grid[0][0].

Hướng tiếp cận

Cách 1 - DSU offline. Sort các ô theo elevation tăng. Lần lượt “kích hoạt” ô và union với 4 hàng xóm đã kích hoạt. Khi (0,0) và (n-1,n-1) cùng component → trả elevation của ô vừa thêm.

Cách 2 - Binary search trên answer + DFS (Chương 37). Cách 3 - Dijkstra (Chương 30).

Cách 1 là pattern DSU đặc trưng nhất.

Code Python 3 

from typing import List

class Solution:
    def swimInWater(self, grid: List[List[int]]) -> int:
        n = len(grid)
        parent = list(range(n * n))
        def find(x):
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x

        # Liệt kê các ô theo elevation tăng.
        cells = sorted((grid[r][c], r, c) for r in range(n) for c in range(n))
        active = [[False] * n for _ in range(n)]
        DIRS = [(-1, 0), (1, 0), (0, -1), (0, 1)]

        for t, r, c in cells:
            active[r][c] = True
            idx = r * n + c
            for dr, dc in DIRS:
                nr, nc = r + dr, c + dc
                if 0 <= nr < n and 0 <= nc < n and active[nr][nc]:
                    parent[find(idx)] = find(nr * n + nc)
            if find(0) == find(n * n - 1):
                return t
        return -1

Phân tích độ phức tạp

  • Thời gian: O(n² · log(n²) + n² · α).
  • Bộ nhớ: O(n²).

Bình luận

  • Pattern “offline sorting + DSU” áp được nhiều bài: LC 1632 (matrix rank), LC 1697 (edge limited paths).

Bài tự luyện liên quan

  • LC 1697 - Checking Existence of Edge Length Limited Paths.
  • LC 1631 - Path With Minimum Effort (Chương 37).

Tóm tắt chương & Quyết định

DSU = “dynamic connectivity, không traversal”

  • Khi đề bài hỏi “sau mỗi thao tác thêm cạnh, có còn k thành phần?” → DSU bắt đầu thắng BFS/DFS (phải redo).
  • Khi đề bài static (snapshot) và chỉ hỏi 1 lần → BFS/DFS thường đủ.

DSU invariant - parent forest 

nodes:  0  1  2  3  4  5
parent: 0  0  0  3  3  5   (sau union(1,0), union(2,1), union(4,3))

forest:
   0           3        5
  / \          |
 1   2         4
  • Mỗi root đại diện 1 component. find(x) đi lên cha đến khi parent[x] == x.

Path compression - before/after 

Before find(4):           After find(4) with compression:
   0                            0
   |                          / | \
   1                         1  2  4
   |                         |
   2                         3  ← 4 trỏ thẳng lên 0 (qua compression)
   |
   3
   |
   4

Number of Islands II (LC 305) - online add

  • Mỗi lần thêm 1 cell (r, c):
    • Đầu tiên count += 1.
    • Với mỗi 4-neighbor đã active: union((r,c), neighbor). Nếu thực sự gộp 2 component khác nhau → count -= 1.
  • DSU rất phù hợp vì BFS lại từ đầu sau mỗi thao tác sẽ là O(k × R × C).

Swim in Rising Water (LC 778) - threshold connectivity

Cầu nối sang Chương 37 (BS + Graph) và Chương 33 (MST): - Sort các ô theo độ cao tăng dần. - Union các ô liền kề đã “ngập” (cùng độ cao đến thời điểm hiện tại). - Khi (0, 0) và (n−1, n−1) rơi vào cùng một component, độ cao hiện tại chính là đáp án.