Number of Islands: flood-fill, BFS, và khi nào Union-Find mới thực sự xứng đáng

Lần đầu tôi gặp bài này, tôi chọn Union-Find ngay. Trông nó rất giống bài toán connected components trong sách giáo khoa, mà Union-Find là cấu trúc dữ liệu textbook cho connected components. Viết xong, pass, cảm thấy ổn được một tuần — cho đến khi đồng nghiệp chỉ ra rằng phiên bản DFS ngắn hơn khoảng một phần ba số dòng và chạy nhanh như nhau. Đôi khi công cụ elegant nhất lại là dư thừa nhất.

Bài toán (LeetCode 200): cho một lưới m x n gồm các ký tự '1' (đất) và '0' (nước), đếm số lượng đảo. Một đảo là nhóm các ô đất liền kề theo chiều ngang hoặc dọc. Tất cả các cạnh biên của lưới đều là nước.

Constraints nói gì

1 <= m, n <= 300. Lưới tối đa 300×300 = 90,000 ô.

Một pass O(m×n) thăm mỗi ô đúng một lần. Với 90,000 ô, điều đó cực kỳ nhanh — dưới một mili giây trên bất kỳ phần cứng hiện đại nào. Constraint này không loại bỏ bất kỳ cách tiếp cận nào và cho phép tất cả: DFS, BFS, Union-Find đều O(m×n) hoặc tốt hơn.

grid[i][j] chỉ là '0' hoặc '1'. Hai trạng thái. Đây là thứ cho phép ta dùng kỹ thuật đánh dấu in-place: lật một ô đất đã thăm từ '1' thành '0', hấp thụ nó vào biển. Không cần mảng visited riêng, không tốn thêm O(m×n) bộ nhớ.

Constraint ngầm mà bài không nói nhưng quan trọng: connectivity 4-chiều (trên, dưới, trái, phải), không phải 8-chiều. Các ô chéo không tính là liền kề. Điều này định hình phần mở rộng neighbor trong mọi cách tiếp cận.

DFS flood-fill

Quan sát cốt lõi: mỗi khi bạn tìm thấy một '1' chưa thăm, bạn vừa tìm thấy ô đầu tiên của một đảo mới. Từ ô đó, DFS có thể tiếp cận và đánh dấu mọi ô khác trên cùng hòn đảo. Khi DFS trả về, cả hòn đảo đã biến mất — lật thành '0' — và vòng lặp ngoài có thể tiếp tục tìm '1' tiếp theo.

class Solution:
    def numIslands(self, grid: list[list[str]]) -> int:
        if not grid or not grid[0]:
            return 0
 
        rows, cols = len(grid), len(grid[0])
        num_islands = 0
 
        def dfs(r, c):
            if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != '1':
                return
            grid[r][c] = '0'
            dfs(r - 1, c)
            dfs(r + 1, c)
            dfs(r, c - 1)
            dfs(r, c + 1)
 
        for i in range(rows):
            for j in range(cols):
                if grid[i][j] == '1':
                    num_islands += 1
                    dfs(i, j)
 
        return num_islands

public class Solution {
    public int NumIslands(char[][] grid) {
        if (grid == null || grid.Length == 0) return 0;
 
        int rows = grid.Length, cols = grid[0].Length;
        int numIslands = 0;
 
        void DFS(int r, int c) {
            if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] != '1') return;
            grid[r][c] = '0';
            DFS(r - 1, c);
            DFS(r + 1, c);
            DFS(r, c - 1);
            DFS(r, c + 1);
        }
 
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == '1') {
                    numIslands++;
                    DFS(i, j);
                }
            }
        }
 
        return numIslands;
    }
}

Recursion kết thúc tại các ô biên và các ô '0'. Mọi ô '1' DFS chạm vào đều được lật thành '0', nên không bao giờ thăm lại. Vòng lặp ngoài thấy mỗi ô đúng một lần. Tổng công việc: O(m×n).

Độ sâu call stack trong trường hợp xấu nhất: một hòn đảo hình con rắn uốn qua tất cả 90,000 ô. Độ sâu stack là 90,000 frame. Ổn trong C# (stack mặc định vài MB). Trong Python, recursion limit mặc định là 1,000 — gặp lưới như vậy là crash ngay. Đáng đề cập trong interview.

Time: O(m×n). Space: O(m×n) trong trường hợp xấu nhất từ call stack.

Trace tay qua Example 2

Example 2 có ba đảo:

["1","1","0","0","0"]
["1","1","0","0","0"]
["0","0","1","0","0"]
["0","0","0","1","1"]

Quá trình DFS từng bước:

Sau khi DFS từ (0,0) kết thúc, khối trên-trái đều là '0'. Vòng lặp ngoài không thấy (0,1), (1,0), (1,1) là trigger vì chúng đã bị zero. Tiếp tục đến (2,2) — đảo đơn ô. Rồi (3,3) và (3,4) tạo thành đảo thứ ba.

BFS: logic tương tự, queue tường minh

BFS thay call stack đệ quy bằng một queue tường minh. Cấu trúc đếm đảo hoàn toàn giống: mỗi '1' mới tìm thấy ở vòng lặp ngoài khởi động BFS xóa cả hòn đảo đó trước khi tiếp tục.

Tại sao BFS thay vì DFS? Câu trả lời thẳng thắn: an toàn stack. Python mặc định recursion limit là 1,000. Một đảo 300×300 crash ngay DFS. BFS dùng queue được cấp phát trên heap, xử lý lưới bất kỳ kích thước mà không lo stack.

from collections import deque
 
class Solution:
    def numIslands(self, grid: list[list[str]]) -> int:
        if not grid or not grid[0]:
            return 0
 
        rows, cols = len(grid), len(grid[0])
        num_islands = 0
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
 
        def bfs(start_r, start_c):
            queue = deque([(start_r, start_c)])
            grid[start_r][start_c] = '0'
            while queue:
                r, c = queue.popleft()
                for dr, dc in directions:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == '1':
                        grid[nr][nc] = '0'
                        queue.append((nr, nc))
 
        for i in range(rows):
            for j in range(cols):
                if grid[i][j] == '1':
                    num_islands += 1
                    bfs(i, j)
 
        return num_islands

public class Solution {
    public int NumIslands(char[][] grid) {
        if (grid == null || grid.Length == 0) return 0;
 
        int rows = grid.Length, cols = grid[0].Length;
        int numIslands = 0;
        int[,] directions = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
 
        void BFS(int startR, int startC) {
            var queue = new Queue<(int, int)>();
            queue.Enqueue((startR, startC));
            grid[startR][startC] = '0';
            while (queue.Count > 0) {
                var (r, c) = queue.Dequeue();
                for (int i = 0; i < 4; i++) {
                    int nr = r + directions[i, 0];
                    int nc = c + directions[i, 1];
                    if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == '1') {
                        grid[nr][nc] = '0';
                        queue.Enqueue((nr, nc));
                    }
                }
            }
        }
 
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == '1') {
                    numIslands++;
                    BFS(i, j);
                }
            }
        }
 
        return numIslands;
    }
}

Một điểm khác biệt nhỏ về space: queue BFS tại bất kỳ thời điểm nào chứa "frontier" của hòn đảo đang khám phá. Với đảo có hình dạng chéo, frontier rộng nhất vào khoảng O(min(m,n)). Một lưới 300×300 toàn đất BFS từ góc — queue lớn nhất khoảng ~300 phần tử, không đến mức 90,000 frame như DFS call stack.

Time: O(m×n). Space: O(min(m,n)) cho BFS queue trong trường hợp xấu nhất.

Union-Find

Union-Find mô hình hóa mỗi ô đất là một node. Ban đầu, mỗi ô '1' là component riêng. Ta quét lưới và union các cặp ô đất liền kề. Sau khi xử lý xong toàn bộ lưới, số component còn lại bằng số đảo.

Implementation dùng path compression (trong find) và union by rank để mỗi thao tác find gần như constant — kỹ thuật là O(α(n)) với α là inverse Ackermann function, luôn ≤ 4 với mọi input thực tế.

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.count = 0
 
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # path compression
        return self.parent[x]
 
    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return
        if self.rank[rx] > self.rank[ry]:
            self.parent[ry] = rx
        elif self.rank[rx] < self.rank[ry]:
            self.parent[rx] = ry
        else:
            self.parent[ry] = rx
            self.rank[rx] += 1
        self.count -= 1
 
class Solution:
    def numIslands(self, grid: list[list[str]]) -> int:
        if not grid or not grid[0]:
            return 0
 
        rows, cols = len(grid), len(grid[0])
        uf = UnionFind(rows * cols)
        uf.count = sum(row.count('1') for row in grid)
 
        for i in range(rows):
            for j in range(cols):
                if grid[i][j] == '1':
                    if j + 1 < cols and grid[i][j + 1] == '1':
                        uf.union(i * cols + j, i * cols + j + 1)
                    if i + 1 < rows and grid[i + 1][j] == '1':
                        uf.union(i * cols + j, (i + 1) * cols + j)
 
        return uf.count

public class UnionFind {
    private int[] parent, rank;
    public int Count;
 
    public UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
    }
 
    public int Find(int x) {
        if (parent[x] != x) parent[x] = Find(parent[x]);
        return parent[x];
    }
 
    public void Union(int x, int y) {
        int rx = Find(x), ry = Find(y);
        if (rx == ry) return;
        if (rank[rx] > rank[ry]) parent[ry] = rx;
        else if (rank[rx] < rank[ry]) parent[rx] = ry;
        else { parent[ry] = rx; rank[rx]++; }
        Count--;
    }
}
 
public class Solution {
    public int NumIslands(char[][] grid) {
        if (grid == null || grid.Length == 0) return 0;
 
        int rows = grid.Length, cols = grid[0].Length;
        var uf = new UnionFind(rows * cols);
        foreach (var row in grid)
            foreach (var cell in row)
                if (cell == '1') uf.Count++;
 
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == '1') {
                    if (j + 1 < cols && grid[i][j + 1] == '1')
                        uf.Union(i * cols + j, i * cols + j + 1);
                    if (i + 1 < rows && grid[i + 1][j] == '1')
                        uf.Union(i * cols + j, (i + 1) * cols + j);
                }
            }
        }
 
        return uf.Count;
    }
}

Lưu ý: phiên bản Union-Find chỉ quét neighbor phải và dưới (không phải cả 4 chiều). Đây là chủ ý — khi xử lý ô từ trái sang phải, trên xuống dưới, neighbor bên trái đã được xử lý rồi và đã được union khi ta đến (i,j). Chỉ neighbor phải và dưới là "mới."

Time: O(m×n × α(m×n)) ≈ O(m×n). Space: O(m×n) cho mảng parent và rank.

Bảng so sánh

Edge cases thực sự quan trọng

Lưới rỗng. grid = [] hoặc grid = [[]]. Cả DFS lẫn BFS đều kiểm tra not grid or not grid[0] đầu tiên và trả về 0.

Toàn nước. grid = [["0","0"],["0","0"]]. Vòng lặp ngoài không bao giờ tìm thấy '1', counter là 0. Hàm DFS/BFS không bao giờ được gọi.

Toàn đất. grid = [["1","1"],["1","1"]]. Ô '1' đầu tiên tại (0,0) trigger DFS/BFS flood toàn bộ lưới. Counter tăng lên 1 và không tăng nữa — mọi ô tiếp theo trong vòng lặp ngoài đều thấy '0'. Đúng.

Ô đơn. grid = [["1"]] trả về 1. grid = [["0"]] trả về 0.

Hình dạng phức tạp. Đảo hình L hoặc U vẫn là một connected component. DFS/BFS xử lý không cần logic đặc biệt vì chúng đệ quy qua tất cả neighbor có thể đến. Hình dạng không quan trọng — chỉ connectivity mới quan trọng.

Python recursion limit. Với DFS trên lưới 300×300 toàn đất, Python cần độ sâu đệ quy đến 90,000. Cần sys.setrecursionlimit(90001) hoặc dùng BFS. Trong interview bằng Python, tôi dùng BFS cho khỏi phải giải thích.

Nên dùng cái nào

Tôi chọn BFS trong Python production và DFS trong C# hoặc Go.

Trong Python, recursion limit mặc định là 1,000. Một đảo 300×300 hit ngay lập tức. BFS tránh vấn đề với deque — cùng runtime O(m×n), an toàn thực tế hơn, và không khó viết hơn sau khi đã quen. Lợi thế space (O(min(m,n)) queue vs O(m×n) call stack) là thật sự có giá trị với lưới toàn đất lớn.

Trong C# (và hầu hết compiled languages), call stack vài MB, DFS 90,000 frame là ổn. Code DFS ngắn hơn, recursion đọc như mô tả bài toán. Tôi viết DFS.

Union-Find chỉ đúng chỗ khi bài toán thay đổi: nếu cần xử lý incremental updates (ô chuyển từ nước sang đất theo thời gian), hoặc cần track kích thước đảo hay merge events, Union-Find scale tốt. Với lưới tĩnh và query đếm đơn giản, nó thừa code mà không có lợi thực tế.

Pattern bên dưới

Bài này giới thiệu graph pattern cơ bản nhất trong catalog LeetCode: connected components via flood-fill. Bạn có một tập nodes (ô) với các cạnh ngầm (adjacency), và cần đếm có bao nhiêu nhóm rời nhau.

Matrix encoding là điều mới duy nhất so với bài graph textbook. Không có adjacency list tường minh — bạn tính neighbor on the fly từ (r±1, c) và (r, c±1). Mọi thứ còn lại ánh xạ trực tiếp: DFS/BFS qua đồ thị, đánh dấu visited để tránh cycle, đếm connected components.

Khi nhận ra hình dạng này, bạn sẽ thấy nó trong một lớp bài toán rộng. Lưới thay đổi, giá trị thay đổi, quy tắc connectivity thay đổi — nhưng thuật toán nền vẫn là cùng một khám phá.

Vị trí trong series graphs

Number of Islands là entry point cho graph traversal trên lưới. Nó dạy flood-fill rõ ràng vì bài đủ đơn giản để mechanics không bị che khuất bởi bất cứ thứ gì khác.

Các bài tiếp theo tự nhiên:

• LeetCode 695 — Max Area of Island. Cùng lưới, cùng cấu trúc DFS, nhưng thay vì đếm đảo bạn trả về kích thước đảo lớn nhất. Thread một size counter qua DFS. Thay đổi nhỏ về hình dạng; thứ bạn trả về thay đổi.
• LeetCode 130 — Surrounded Regions. Đánh dấu các ô 'O' không có thể đến từ biên, rồi lật phần còn lại. Cần suy nghĩ về component nào thuộc biên — bài tập tốt về đảo ngược câu hỏi connectivity.
• LeetCode 1020 — Number of Enclaves. Đếm các ô đất không có đường đến biên lưới. Bắt đầu BFS/DFS từ mọi ô đất biên và trừ số đã thăm từ tổng. Flood-fill như nhau, accounting khác nhau.
• LeetCode 694 — Number of Distinct Islands. Đếm đảo có hình dạng khác nhau. Cần canonicalize đường đi trong DFS để lấy chữ ký hình dạng. Union-Find không giúp ở đây; DFS với path recording mới là tool đúng.

Mỗi bài thêm đúng một twist. Làm theo thứ tự và pattern sâu dần theo từng bước.