Union-Find Disjoint Sets (DSU)

Input:

4 2
1 2
2 3

Output:

1 2 3 4 
1 1 1 4

Code C++
Độ phức tạp:
Hàm root : O(logN)
Hàm merge : O(logN)

#include <iostream>
using namespace std;

int lab[1005];

int root(int u) {
    if (lab[u] < 0) return u;
    return lab[u] = root(lab[u]);
}

void merge(int u, int v) {
    u = root(u);
    v = root(v);
    if (u == v) return;
    if (lab[u] > lab[v]) swap(u, v);
    lab[u] += lab[v];
    lab[v] = u;
}

int main() {
    
    memset(lab, -1, sizeof lab);
    
    int n, m; cin >> n >> m;
    for(int i = 0; i < m; i++) {
        int u, v; cin >> u >> v;
        merge(u, v);
    }
    
    for(int u = 1; u <= n; u++) cout << u << ' ';
    cout << '\n';
    for(int u = 1; u <= n; u++) cout << root(u) << ' ';
        
    return 0;
}

Ghi chú:
– Ý nghĩa mảng lab[], xét đỉnh u trong 1 thành phần liên thông:
+ Nếu u không phải là gốc (root) thì lab[u] = cha của u
+ Nếu u là gốc thì lab[u] < 0 và |lab[u]| = số lượng đỉnh của thành phần liên thông đó
Khởi tạo lab[u] = -1 với mọi u

– Tại mọi thời điểm, muốn truy vấn cha của u, phải dùng root(u) thay cho lab[u] (vì lab[u] lúc này có thể chưa được "nén")

– Khi merge thì ta sẽ nối thành phần liên thông có ít đỉnh hơn vào thành phần liên thông có nhiều đỉnh hơn, vì như vậy sẽ làm cho thuật toán nén đường ở hàm root tối ưu hơn.

Happy coding,

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s