DSU (còn gọi là Union-Find) là cấu trúc dữ liệu quản lý các tập hợp rời nhau (disjoint sets). Hỗ trợ hai thao tác chính:
- Find: Tìm đại diện (root) của tập chứa phần tử .
- Union: Gộp hai tập chứa và .
Cài đặt với hai tối ưu
Hai tối ưu giúp DSU đạt gần mỗi thao tác:
- Path Compression: Khi
find(x), trỏ tất cả node trên đường đi thẳng lên root. - Union by Size: Gộp cây nhỏ vào cây lớn.
C++
struct DSU {
vector<int> parent, size;
DSU(int n) : parent(n), size(n, 1) {
iota(parent.begin(), parent.end(), 0);
}
int find(int x) {
if (parent[x] != x)
parent[x] = find(parent[x]); // path compression
return parent[x];
}
bool unite(int x, int y) {
x = find(x); y = find(y);
if (x == y) return false;
if (size[x] < size[y]) swap(x, y);
parent[y] = x;
size[x] += size[y];
return true;
}
bool connected(int x, int y) {
return find(x) == find(y);
}
};
Python
class DSU:
def __init__(self, n):
self.parent = list(range(n))
self.size = [1] * n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def unite(self, x, y):
x, y = self.find(x), self.find(y)
if x == y:
return False
if self.size[x] < self.size[y]:
x, y = y, x
self.parent[y] = x
self.size[x] += self.size[y]
return True
def connected(self, x, y):
return self.find(x) == self.find(y)
Độ phức tạp
mỗi thao tác — là hàm Ackermann ngược, thực tế coi như .
Ứng dụng
Thuật toán Kruskal (cây khung nhỏ nhất)
sort(edges.begin(), edges.end()); // {weight, u, v}
DSU dsu(n);
long long total = 0;
for (auto [w, u, v] : edges) {
if (dsu.unite(u, v))
total += w;
}
Đếm số thành phần liên thông
DSU dsu(n);
for (auto [u, v] : edges) dsu.unite(u, v);
unordered_set<int> roots;
for (int i = 0; i < n; i++) roots.insert(dsu.find(i));
cout << roots.size();
Kiểm tra chu trình
DSU dsu(n);
for (auto [u, v] : edges) {
if (!dsu.unite(u, v)) {
cout << "Có chu trình!";
break;
}
}
Bình luận