Tổng hợp câu hỏi phỏng vấn union-find: path compression, tính liên thông và Java template

Union-find chuyên giải quyết các vấn đề về “phân nhóm” và “tính liên thông”. Hai phần tử có thuộc cùng một nhóm không? Sau khi hợp nhất hai set còn bao nhiêu connected components? Thêm một edge vào graph có tạo thành cycle không? Tất cả đều có thể xử lý bằng union-find.

Trong phỏng vấn, code không dài, nhưng nếu viết find không tốt thì sẽ ảnh hưởng trực tiếp đến complexity.

Tổng quan nội dung:

1. Union-find là gì?
2. Union-find biểu diễn set bằng array như thế nào?
3. find, union, connected lần lượt làm gì?
4. Vì sao path compression và union by size có thể tăng tốc?
5. Union-find phù hợp với những vấn đề về tính liên thông nào?

Union-find là gì?

Union-find (Disjoint Set Union, DSU, còn gọi là Union Find) duy trì một nhóm các set đôi một không giao nhau. Nó đặc biệt phù hợp để trả lời hai loại vấn đề:

1. Truy vấn: hiện tại hai phần tử có thuộc cùng một set không?
2. Hợp nhất: hợp nhất hai set chứa hai phần tử thành một set.

Nó không quan tâm đến cấu trúc đầy đủ bên trong set, cũng không quan tâm giữa hai node cụ thể đã đi qua những edge nào. Ví dụ trong quan hệ xã hội, union-find có thể nhanh chóng cho bạn biết A và B có thuộc cùng một mạng lưới quan hệ không; nhưng nó không cho bạn biết shortest path từ A đến B là gì.

Đây cũng là điểm khác nhau giữa union-find và BFS/DFS: BFS/DFS giống như mỗi lần đều search trực tiếp trên graph; còn union-find duy trì quan hệ liên thông trong quá trình hợp nhất, để các truy vấn sau chỉ cần kiểm tra representative node của hai phần tử có giống nhau không.

Union-find biểu diễn set như thế nào?

Union-find thường dùng một array parent để biểu diễn một forest gồm nhiều tree:

• parent[x] biểu thị parent node của phần tử x.
• Nếu parent[x] == x, nghĩa là x là root node của set tương ứng.
• Một set chỉ cần dùng root node làm representative.

Khi khởi tạo, mỗi phần tử là một set riêng biệt, nên parent node của mỗi phần tử chính là nó:

parent[0] = 0
parent[1] = 1
parent[2] = 2
...

Sau khi thực hiện union(0, 1), có thể gắn root node của 1 vào bên dưới root node của 0. Khi đó 0 và 1 thuộc cùng một set. Tiếp tục thực hiện union(1, 2), dù truyền vào 1 và 2, nhưng thứ thực sự được hợp nhất là root node của 1 và root node của 2.

Vì vậy, điểm mấu chốt trong union-find không phải là “parent node hiện tại của node là ai”, mà là “lần theo các parent node lên trên, cuối cùng xác định root node là ai”. find(x) thực hiện chính việc này.

Ba thao tác cốt lõi

Các thao tác thường gặp của union-find có thể khái quát thành ba thao tác:

Thao tác	Tác dụng
find(x)	Tìm representative node của set chứa x, cũng chính là root node
union(a, b)	Hợp nhất hai set chứa a và b
connected(a, b)	Kiểm tra representative node của a và b có giống nhau không

Nếu root node của hai phần tử giống nhau, nghĩa là chúng đã thuộc cùng một set; nếu root node khác nhau, union sẽ gắn một root node vào bên dưới root node kia.

Trọng tâm phỏng vấn

• Có thể tự viết find và union.
• Có thể giải thích tác dụng của path compression.
• Có thể dùng union-find để đếm connected components.
• Có thể xử lý cycle detection trong graph, bài toán friend circle, số lượng tỉnh và quan hệ đẳng thức.
• Có thể giải thích union-find phù hợp với việc merge động nhưng không phù hợp với việc xóa thường xuyên.

Từ Quick Find đến Quick Union

Khi tìm hiểu union-find, có thể xem trước hai phiên bản cực đoan:

• Quick Find: array lưu trực tiếp mã set mà mỗi phần tử thuộc về. Truy vấn hai phần tử có cùng nhóm rất nhanh, nhưng khi hợp nhất hai set thì phải quét toàn bộ array để sửa mã set.
• Quick Union: array lưu parent node và dùng root node để đại diện cho set. Khi hợp nhất chỉ cần sửa parent pointer của một root node, nhưng nếu tree quá cao thì find sẽ chậm.

Trong phỏng vấn và làm bài, phiên bản tối ưu của Quick Union thường được dùng: path compression + union by size/rank.

• Path compression: mỗi lần find(x), gắn trực tiếp các node trên đường đi vào bên dưới root node, để những lần truy vấn sau nhanh hơn.
• Union by size: khi hợp nhất hai set, gắn tree nhỏ vào bên dưới tree lớn để hạn chế chiều cao của tree.

Kết hợp hai tối ưu này có thể khiến thời gian của nhiều thao tác union-find gần như hằng số.

Template cơ bản

class UnionFind {
    private final int[] parent;
    private final int[] size;
    private int count;

    UnionFind(int n) {
        parent = new int[n];
        size = new int[n];
        count = n;
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }

    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    boolean union(int a, int b) {
        int rootA = find(a);
        int rootB = find(b);
        if (rootA == rootB) {
            return false;
        }
        if (size[rootA] < size[rootB]) {
            parent[rootA] = rootB;
            size[rootB] += size[rootA];
        } else {
            parent[rootB] = rootA;
            size[rootA] += size[rootB];
        }
        count--;
        return true;
    }

    boolean connected(int a, int b) {
        return find(a) == find(b);
    }

    int count() {
        return count;
    }
}

parent[x] biểu thị parent node của x. Parent node của root node là chính nó. Path compression sẽ khiến các node trên đường đi được gắn trực tiếp vào bên dưới root node, giúp những lần truy vấn sau nhanh hơn.

Template này có hai chi tiết đáng xem riêng:

1. parent[x] = find(parent[x]) trong find() là path compression. Sau khi recursion trả về root node, phép gán này đồng thời nối trực tiếp x với root node.
2. union() dùng size để quyết định root node nào được gắn bên dưới root node nào, đây là union by size. Cách này giúp hạn chế chiều cao của tree tăng lên.

count biểu thị số connected components hiện còn. Mỗi lần union() thực sự hợp nhất hai set vốn không liên thông, count mới giảm 1; nếu hai phần tử vốn đã liên thông thì không được giảm thêm.

Độ phức tạp

Sau khi dùng path compression và union by size, amortized complexity của một thao tác union-find là O(α(n)), trong đó α(n) là inverse Ackermann function, tăng cực kỳ chậm. Trong phỏng vấn thực tế, thường chỉ cần nói “thời gian gần như hằng số” là đủ.

Space complexity là O(n), chủ yếu đến từ hai array parent và size.

Trường hợp sử dụng điển hình

Trường hợp sử dụng	Cách xử lý
Kiểm tra hai node có liên thông không	So sánh find(a) và find(b)
Hợp nhất hai set	union(a, b)
Đếm số connected components	Khởi tạo bằng n, mỗi lần hợp nhất thành công thì giảm 1
Kiểm tra graph vô hướng có cycle không	Nếu hai đầu của một edge đã liên thông, thêm edge sẽ tạo cycle
Phương trình đẳng thức	Hợp nhất các quan hệ bằng nhau trước, sau đó kiểm tra các quan hệ khác nhau có xung đột không

Union-find đặc biệt phù hợp với những vấn đề “các quan hệ liên tục được hợp nhất và cần truy vấn có cùng nhóm hay không”, chẳng hạn số lượng tỉnh, kết nối dư thừa, hợp nhất account và thuật toán Kruskal trong minimum spanning tree.

Tuy nhiên, union-find không giỏi xử lý việc xóa quan hệ. Vì một khi hai set đã được hợp nhất, thông tin về những edge nào tạo ra tính liên thông thường đã bị nén mất. Sau khi xóa một edge, không thể xác định các set còn liên thông hay không chỉ bằng cách sửa đơn giản array parent.

Điểm dễ sai

• Trong find, phải trả về root node, không phải parent node.
• Khi thực hiện path compression, không được bỏ qua giá trị trả về của recursion.
• Khi union, chỉ khi hai set vốn không liên thông thì số connected components mới giảm 1.
• Union-find phù hợp với việc hợp nhất, không giỏi xử lý xóa quan hệ.
• Bài toán grid hai chiều cần ánh xạ (i, j) thành chỉ số một chiều, ví dụ i * cols + j.

Bài tập đề xuất

• 547. Number of Provinces
• 684. Redundant Connection
• 990. Satisfiability of Equality Equations
• 1319. Number of Operations to Make Network Connected
• 200. Number of Islands

Tài liệu tham khảo

• Algorithms, 4th Edition: Union-Find
• Algorithms, 4th Edition: WeightedQuickUnionPathCompressionUF
• CP-Algorithms: Disjoint Set Union

Lời cuối

Nếu nội dung hữu ích với bạn, hãy tiện tay tặng JavaGuide một Star miễn phí để ủng hộ: GitHub | Gitee.

JavaGuide đã được duy trì gần bảy năm, tích lũy 6100+ commit, với sự chung tay hoàn thiện của 620+ contributor. Star, phản hồi và PR của bạn đều là động lực để dự án tiếp tục cập nhật.

Nếu bạn đang chuẩn bị phỏng vấn backend / phát triển ứng dụng AI, có thể tham khảo Knowledge Planet của tôi, bao gồm các project thực tế về backend và AI, tối ưu CV, hỏi đáp 1-1 và tài liệu về các trọng điểm thường gặp, đã được duy trì liên tục sáu năm.