DSU Union Find: gộp nhóm, nén đường đi và đếm thành phần

DSU giải quyết kiểu truy vấn nào?

Ban đầu có năm phần tử 0 tới 4, mỗi phần tử là một nhóm riêng. Sau thao tác nối 0 với 1, hai phần tử đó cùng nhóm. Nối tiếp 3 với 4 tạo một nhóm khác. Khi nối 1 với 4, cả hai nhóm gộp thành {0,1,3,4}, dù ta không nối trực tiếp mọi cặp trong nhóm.

DSU giúp trả lời “0 và 3 có chung nhóm không?” và “nhóm của 4 có bao nhiêu phần tử?” sau nhiều lần gộp. Nó không lưu đường đi thật giữa các phần tử. Các liên kết cha của DSU chỉ phục vụ quản lý đại diện, không nhất thiết là các cạnh của đồ thị ban đầu.

Biểu diễn bằng parent và gốc

Mỗi phần tử có một parent. Nếu parent[x] == x, x là gốc và đại diện cho nhóm của nó. Nếu không, đi tiếp theo parent cho tới gốc. Hàm find trả gốc này. Hai phần tử cùng nhóm khi và chỉ khi find của chúng bằng nhau.

Đừng so sánh parent[a] == parent[b] rồi kết luận khác nhóm khi hai giá trị khác. Hai nhánh trung gian có thể vẫn dẫn về cùng một gốc. Ngược lại, ID của gốc không có ý nghĩa “nhỏ nhất nhóm” hoặc “người đầu tiên của nhóm” nếu thuật toán không thiết kế thêm quy tắc đó.

Ban đầu đặt parent[i] = i, size[i] = 1 và groups = n. Mảng size chỉ có ý nghĩa kích thước nhóm tại gốc. Khi cần kích thước nhóm của x, đọc size[find(x)], không đọc size[x] nếu x đã trở thành một nút con.

Gộp theo kích thước tránh cây cao

Muốn gộp a và b, trước hết tìm hai gốc ra và rb. Nếu hai gốc bằng nhau, hai phần tử đã cùng nhóm; trả false và không đổi groups. Nếu khác, đặt gốc của nhóm nhỏ làm con của gốc nhóm lớn, rồi cộng hai kích thước và giảm groups một.

Vì sao cách này tốt hơn nối tùy ý? Mỗi lần một phần tử thuộc nhóm nhỏ bị đưa xuống dưới nhóm lớn, nhóm chứa nó có ít nhất gấp đôi số phần tử trước đó. Không thể nhân đôi hơn O(log n) lần khi chỉ có n phần tử, nên gộp theo kích thước đã giới hạn độ sâu tốt hơn cây cha tạo tùy ý.

Trong ví dụ, gộp 0–1 và 3–4 thành hai nhóm cỡ 2. Gộp 1–4 thật ra tìm về hai gốc của các nhóm, rồi nối một gốc vào gốc kia. Kích thước nhóm mới là 4; phần tử 2 vẫn độc lập. Gọi lại thao tác gộp 0–3 không làm kích thước tăng thêm vì chúng đã cùng nhóm.

Nén đường đi khi find

Nếu một đường cha là x tới p tới gốc r, sau khi biết r, ta có thể cho các nút trên đường trỏ gần gốc hơn. Lần tìm sau sẽ đi ít bước. Quan hệ các nhóm không đổi vì mọi nút vẫn thuộc cùng cây đại diện.

Code dùng một biến thể lặp là path halving: trong lúc đi lên, cho parent[x] trỏ tới ông của x rồi chuyển x lên parent mới. Nó không cần đệ quy nên tránh tạo thêm một chuỗi lời gọi Python dài. Cách nén toàn bộ đường bằng đệ quy cũng phổ biến, nhưng không được trộn việc tìm gốc với thay đổi đại diện tùy ý.

Kết hợp nén đường đi và gộp theo kích thước cho chi phí khấu hao O(α(n)) mỗi thao tác trong phân tích chuẩn, với α là hàm ngược Ackermann tăng rất chậm. Đây là kết luận trên cả chuỗi thao tác, không có nghĩa từng lời gọi find riêng lẻ luôn chỉ thực hiện đúng một phép đọc mảng.

Code C++ và Python chạy ví dụ

#include <iostream>
#include <numeric>
#include <tuple>
#include <vector>
using namespace std;
class DSU{
    vector<int> p,sz;
public:
    int groups;
    explicit DSU(int n):p(n),sz(n,1),groups(n){iota(p.begin(),p.end(),0);}
    int find(int x){while(p[x]!=x){p[x]=p[p[x]];x=p[x];}return x;}
    bool unite(int a,int b){
        a=find(a);b=find(b);if(a==b)return false;
        if(sz[a]<sz[b])swap(a,b);
        p[b]=a;sz[a]+=sz[b];--groups;return true;
    }
    bool same(int a,int b){return find(a)==find(b);}
    int size(int a){return sz[find(a)];}
};
int main(){
    int n=5,q;vector<tuple<char,int,int>>ops={{'U',0,1},{'U',3,4},{'Q',0,4},{'U',1,4},{'Q',0,3},{'S',4,0}};
    if(cin>>n>>q){ops.clear();for(int i=0;i<q;++i){char c;int a,b=0;cin>>c>>a;if(c!='S')cin>>b;ops.emplace_back(c,a,b);}}
    DSU d(n);
    for(auto[c,a,b]:ops){if(c=='U')cout<<d.unite(a,b);else if(c=='Q')cout<<d.same(a,b);else cout<<d.size(a);cout<<'\n';}
    cout<<d.groups<<'\n';
}

class DSU:
    def __init__(self,n):
        self.parent=list(range(n))
        self.sz=[1]*n
        self.groups=n
    def find(self,x):
        while self.parent[x]!=x:
            self.parent[x]=self.parent[self.parent[x]]
            x=self.parent[x]
        return x
    def unite(self,a,b):
        a,b=self.find(a),self.find(b)
        if a==b:return False
        if self.sz[a]<self.sz[b]:a,b=b,a
        self.parent[b]=a
        self.sz[a]+=self.sz[b]
        self.groups-=1
        return True
    def same(self,a,b):
        return self.find(a)==self.find(b)
    def size(self,a):
        return self.sz[self.find(a)]

if __name__=='__main__':
    import sys
    lines=sys.stdin.read().splitlines()
    if lines:
        n,q=map(int,lines[0].split());ops=[line.split() for line in lines[1:1+q]]
    else:
        n=5;ops=[['U',0,1],['U',3,4],['Q',0,4],['U',1,4],['Q',0,3],['S',4]]
    d=DSU(n)
    for c,a,*rest in ops:
        a=int(a)
        if c=='U':print(int(d.unite(a,int(rest[0]))))
        elif c=='Q':print(int(d.same(a,int(rest[0]))))
        else:print(d.size(a))
    print(d.groups)

Ví dụ mặc định in lần lượt 1 1 0 1 1 4 2, mỗi số trên một dòng. Hai số 1 đầu nghĩa là hai lần gộp tạo nhóm mới. Số 0 là truy vấn 0 và 4 chưa chung nhóm. Lần gộp tiếp theo thành công, rồi truy vấn 0 và 3 cho 1, kích thước nhóm của 4 bằng 4 và tổng số nhóm còn 2.

Nhập riêng bằng dòng n, q rồi q lệnh. U a b gộp hai nhóm và in 1 nếu thật sự đổi cấu trúc nhóm; Q a b kiểm cùng nhóm; S a hỏi kích thước. Cuối chương trình luôn in số nhóm. Chỉ số hợp lệ từ 0 tới n−1; n = 0 chỉ có thể dùng khi không truy vấn phần tử nào.

Code C++ dùng vector và iota để khởi tạo đại diện. Python dùng list(range(n)). Khởi tạo cần O(n) thời gian và O(n) bộ nhớ. Phần lưu input/output của một chương trình hoàn chỉnh còn có chi phí riêng; khi bàn độ phức tạp DSU, tách rõ dữ liệu quản lý nhóm với dữ liệu các lệnh.

DSU và đồ thị: làm được gì, không làm được gì?

Nếu đồ thị vô hướng chỉ thêm cạnh, mỗi cạnh mới gộp hai nhóm đầu mút. Sau đó dùng same để hỏi có đường nối giữa hai đỉnh hay không. Khi cạnh có hai đầu đã cùng nhóm, nó không làm giảm số thành phần liên thông. Đây cũng là ý tưởng kiểm chu trình trong Kruskal khi xét các cạnh theo trọng số.

DSU cơ bản không trả đường đi ngắn nhất, không phân biệt hướng cạnh và không tự xử lý việc xóa cạnh làm tách một nhóm. Với đồ thị có hướng, cùng nhóm sau khi bỏ hướng không đồng nghĩa hai đỉnh đi tới nhau theo cả hai chiều. Hãy chọn đúng mô hình trước khi dùng union find cho mọi bài có từ “kết nối”.

Một số bài xóa cạnh có thể xử lý ngược thời gian, biến xóa thành thêm; các bài khác cần DSU rollback hoặc kỹ thuật nâng cao. Không thêm hàm “tách” chỉ bằng gán parent một đỉnh về chính nó: các phần tử phụ thuộc phía dưới có thể bị chia sai.

Lỗi hay gặp và kiểm bằng mô hình đơn giản

Để tự kiểm tra DSU trên dữ liệu nhỏ, bạn có thể dùng một mảng nhãn nhóm đơn giản: mỗi khi gộp hai tập, quét toàn bộ mảng để đổi nhãn của một nhóm sang nhóm còn lại. Cách làm O(n) mỗi truy vấn này hoàn toàn tách biệt với cây parent, rất tiện để đối chiếu các ca một phần tử, gộp lặp cùng một cạnh và chuỗi truy vấn ngẫu nhiên.

Luyện ngay trên Big-O Coding

Ba bài dưới luyện thao tác gộp nhóm, kiểm tra kết nối và quản lý kích thước thành phần. Hãy làm theo thứ tự, bắt đầu từ cấu trúc DSU cơ bản trước khi thêm thông tin phụ cho mỗi nhóm.

Câu hỏi thường gặp

Nguồn tham khảo

• cp-algorithms: Disjoint Set Union
• cp-algorithms: Kruskal with DSU
• MIT: Introduction to Algorithms