Disjoint Set Union (DSU)

Mức độ: Nâng cao

Có n người, lần lượt có tin “người u và người v là bạn”. Bạn của bạn cũng tính là cùng nhóm. Sau mỗi tin, hỏi “x và y có cùng nhóm không?”. Mỗi lần hỏi chạy BFS từ x thì mất tới n bước. DSU (Disjoint Set Union, còn gọi là Union-Find) trả lời mỗi câu hỏi và gộp mỗi nhóm gần như tức thì.

Ý tưởng: mỗi nhóm có một “trưởng nhóm”

Mỗi nhóm được biểu diễn bằng một cây: mỗi người lưu cha[x], người đứng đầu (gốc cây) có cha[x] = x và là trưởng nhóm.

• Tìm trưởng nhóm của x: đi theo cha cho đến khi gặp gốc.
• Hai người cùng nhóm khi có cùng trưởng nhóm.
• Gộp hai nhóm: tìm hai trưởng nhóm, cho trưởng nhóm này làm cha của trưởng nhóm kia.

Bốn người 1 2 3 4, lần lượt gộp (1, 2), (3, 4), (2, 4):

Thao tác	cha[1]	cha[2]	cha[3]	cha[4]	Các nhóm
ban đầu	1	2	3	4	1 | 2 | 3 | 4
gộp 1, 2	1	1	3	4	1 2 | 3 | 4
gộp 3, 4	1	1	3	3	1 2 | 3 4
gộp 2, 4	1	1	1	3	1 2 3 4

Ở bước cuối, trưởng nhóm của 2 là 1, của 4 là 3, nên cho cha[3] = 1.

Hai cải tiến làm DSU rất nhanh

Nếu gộp tùy tiện, cây có thể thành một đường dài n, tìm trưởng nhóm mất n bước. Hai cải tiến:

1. Gộp theo kích thước: luôn gắn gốc của nhóm nhỏ hơn vào gốc của nhóm lớn hơn. Mỗi lần một người bị “chuyển xuống” một tầng thì nhóm của người đó ít nhất to gấp đôi, nên cây không cao quá log₂n tầng.
2. Nén đường đi: khi tìm trưởng nhóm của x, cho mọi người trên đường đi trỏ thẳng vào gốc. Lần sau tìm lại chỉ mất một bước.

Dùng cả hai thì mỗi thao tác trung bình chỉ mất vài bước (về lý thuyết là một hàm tăng cực kỳ chậm, với mọi n trong đề thi đều không quá 5).

Python

import sys

def tim(x):
    goc = x
    while cha[goc] != goc:
        goc = cha[goc]
    while cha[x] != goc:          # nén đường đi
        cha[x], x = goc, cha[x]
    return goc

def gop(u, v):
    u, v = tim(u), tim(v)
    if u == v:
        return False              # đã cùng nhóm
    if kich_thuoc[u] < kich_thuoc[v]:
        u, v = v, u
    cha[v] = u                    # gắn nhóm nhỏ vào nhóm lớn
    kich_thuoc[u] += kich_thuoc[v]
    return True

du_lieu = sys.stdin.read().split()
n, q = int(du_lieu[0]), int(du_lieu[1])
cha = list(range(n + 1))
kich_thuoc = [1] * (n + 1)
ket_qua = []
for t in range(q):
    loai, u, v = du_lieu[2 + 3 * t], int(du_lieu[3 + 3 * t]), int(du_lieu[4 + 3 * t])
    if loai == '1':
        gop(u, v)
    else:
        ket_qua.append("YES" if tim(u) == tim(v) else "NO")
print("\n".join(ket_qua))

C++

#include <iostream>
#include <vector>
#include <numeric>
using namespace std;

vector<int> cha, kichThuoc;

int tim(int x) {
    if (cha[x] == x) return x;
    return cha[x] = tim(cha[x]);   // nén đường đi
}

bool gop(int u, int v) {
    u = tim(u), v = tim(v);
    if (u == v) return false;      // đã cùng nhóm
    if (kichThuoc[u] < kichThuoc[v]) swap(u, v);
    cha[v] = u;                    // gắn nhóm nhỏ vào nhóm lớn
    kichThuoc[u] += kichThuoc[v];
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    cha.resize(n + 1);
    iota(cha.begin(), cha.end(), 0);
    kichThuoc.assign(n + 1, 1);
    while (q--) {
        int loai, u, v;
        cin >> loai >> u >> v;
        if (loai == 1) gop(u, v);
        else cout << (tim(u) == tim(v) ? "YES" : "NO") << "\n";
    }
    return 0;
}

Lưu ý: trong Python, hàm tim viết bằng vòng lặp thay vì đệ quy, vì cây có thể sâu tới hàng nghìn tầng trước khi được nén, đệ quy dễ vượt giới hạn. Trong C++ đệ quy vẫn ổn nhờ gộp theo kích thước giữ cây thấp.

DSU dùng được cho những gì?

Câu hỏi	Cách dùng
số nhóm (thành phần liên thông)	bắt đầu với n nhóm, mỗi lần gop thành công thì bớt 1
cạnh nào tạo chu trình	cạnh (u, v) mà u, v đã cùng nhóm
kích thước nhóm của x	kich_thuoc[tim(x)]
xóa dần cạnh	DSU chỉ gộp được, không tách được: đi ngược thời gian, coi xóa là thêm
cây khung nhỏ nhất	thuật toán Kruskal

Luyện tập

Gồm 20 bài, chia thành 6 nhóm từ dễ đến khó. Mỗi bài có một dữ liệu kiểm tra: các bạn chạy chương trình của mình với dữ liệu đó rồi so với đáp số.

Nhóm 1. Gộp nhóm và đếm

Bài 1. Số thành phần liên thông

Có n thành phố và m con đường hai chiều. Dòng đầu có n, m (1 ≤ n ≤ 10⁵, 0 ≤ m ≤ 2 × 10⁵), m dòng sau mỗi dòng có u, v (có thể u = v hoặc có đường lặp lại). In ra số nhóm thành phố, hai thành phố cùng nhóm khi đi được tới nhau.

Ví dụ:

Nhập	In ra
6 4 1 2 2 3 4 5 3 1	3

Kiểm tra: nhập

10 7
1 5
5 9
2 2
3 4
4 8
8 3
10 6

Xem đáp số

5

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 2. Có cùng nhóm không

Dòng đầu có n, q (1 ≤ n, q ≤ 2 × 10⁵), q dòng sau mỗi dòng là một thao tác 1 u v (u và v thành bạn) hoặc 2 u v (hỏi u và v có cùng nhóm bạn không). Với mỗi thao tác loại 2, in ra YES hoặc NO.

Ví dụ:

Nhập	In ra
5 6 1 1 2 2 1 3 1 2 3 2 1 3 1 4 5 2 3 5	NO YES NO

Kiểm tra: nhập

8 8
1 1 2
1 3 4
2 2 4
1 2 3
2 1 4
1 6 7
2 7 8
2 6 6

Xem đáp số

NO
YES
NO
YES

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 3. Nhóm lớn nhất sau mỗi lần kết bạn

Dòng đầu có n, m (1 ≤ n ≤ 10⁵, 1 ≤ m ≤ 2 × 10⁵), m dòng sau mỗi dòng có u, v: u và v thành bạn. Sau mỗi lần kết bạn, in ra (trên một dòng, cách nhau dấu cách) số người của nhóm đông nhất.

Ví dụ:

Nhập	In ra
6 4 1 2 3 4 2 3 5 6	2 2 4 4

Kiểm tra: nhập

8 6
1 2
3 4
5 6
7 8
1 8
2 7

Xem đáp số

2 2 2 2 4 4

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 4. Con đường đầu tiên tạo vòng

Dòng đầu có n, m (1 ≤ n ≤ 10⁵, 1 ≤ m ≤ 2 × 10⁵), m dòng sau mỗi dòng có u, v (u khác v): lần lượt xây đường hai chiều nối u và v. In ra số thứ tự (từ 1) của con đường đầu tiên mà sau khi xây, mạng đường có một vòng (đi từ một thành phố qua các con đường khác nhau rồi quay về), hoặc 0 nếu không bao giờ có vòng.

Ví dụ:

Nhập	In ra
5 5 1 2 2 3 4 5 3 1 1 4	4

Kiểm tra: nhập

8 7
1 2
3 4
5 6
2 3
6 7
8 5
4 1

Xem đáp số

7

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 5. Đường thừa

Có n thành phố và m con đường hai chiều (có thể có đường nối một thành phố với chính nó, hoặc nhiều đường nối cùng hai thành phố). Dòng đầu có n, m (1 ≤ n ≤ 10⁵, 0 ≤ m ≤ 2 × 10⁵), m dòng sau mỗi dòng có u, v. In ra số đường nhiều nhất có thể phá bỏ mà hai thành phố nào trước đi được tới nhau thì vẫn đi được.

Ví dụ:

Nhập	In ra
5 6 1 2 2 3 3 1 4 5 4 5 2 2	3

Kiểm tra: nhập

10 12
1 2
2 3
3 4
4 1
1 3
5 6
6 7
7 5
8 8
9 10
10 9
9 10

Xem đáp số

6

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 6. Đếm cặp liên lạc được

Dòng đầu có n, m (1 ≤ n ≤ 10⁵, 0 ≤ m ≤ 2 × 10⁵), m dòng sau mỗi dòng có u, v: hai máy tính u, v nối với nhau. In ra số cặp máy (không kể thứ tự, hai máy khác nhau) liên lạc được với nhau qua các đường nối.

Ví dụ:

Nhập	In ra
6 4 1 2 2 3 4 5 6 6	4

Kiểm tra: nhập

10 6
1 2
3 4
4 5
5 3
7 8
9 7

Xem đáp số

7

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 2. DSU trên bảng

Bài 7. Đếm đảo

Bản đồ là bảng m hàng, n cột gồm # (đất) và . (nước). Hai ô đất chung cạnh thuộc cùng một đảo. Dòng đầu có m, n (1 ≤ m, n ≤ 1000), m dòng sau mỗi dòng là một xâu n ký tự. In ra số đảo.

Ví dụ:

Nhập	In ra
4 5 ##..# #...# ..#.. ....#	4

Kiểm tra: nhập

6 7
#.#.#.#
###.###
.......
#######
#.....#
#.###.#

Xem đáp số

4

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 8. Đảo mọc lên

Biển là bảng m hàng, n cột, ban đầu toàn nước. Lần lượt có k lần một ô (r, c) nổi lên thành đất (một ô có thể nổi lên nhiều lần, lần sau không thay đổi gì). Dòng đầu có m, n, k (1 ≤ m, n ≤ 1000, 1 ≤ k ≤ 10⁵), k dòng sau mỗi dòng có r, c. Sau mỗi lần, in ra số đảo (cách nhau dấu cách).

Ví dụ:

Nhập	In ra
3 3 5 1 1 1 3 1 2 3 3 2 3	1 2 1 2 1

Kiểm tra: nhập

4 4 7
1 1
2 2
1 2
4 4
3 3
2 3
3 4

Xem đáp số

1 2 1 2 3 2 1

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 9. Bạn của bạn

Dòng đầu có n, m, q (1 ≤ n ≤ 10⁵, 0 ≤ m ≤ 2 × 10⁵, 1 ≤ q ≤ 10⁵), m dòng sau mỗi dòng có u, v: u và v là bạn; q dòng sau mỗi dòng có một người x. Với mỗi x, in ra số người khác x cùng nhóm bạn với x (bạn của bạn cũng tính).

Ví dụ:

Nhập	In ra
6 3 3 1 2 2 3 5 6 1 4 6	2 0 1

Kiểm tra: nhập

10 6 4
1 2
3 4
4 5
2 5
7 8
8 9
1
7
10
5

Xem đáp số

4
2
0
4

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 3. Sắp xếp rồi gộp, đi ngược thời gian

Bài 10. Ngày đầu tiên thông suốt

Có n thành phố, chưa có đường nào. Lần lượt mỗi ngày xây một con đường hai chiều. Dòng đầu có n, m (2 ≤ n ≤ 10⁵, 1 ≤ m ≤ 2 × 10⁵), dòng thứ i trong m dòng sau có u, v: đường xây ngày thứ i. In ra ngày đầu tiên mà từ mọi thành phố đi được tới mọi thành phố khác, hoặc -1 nếu đến hết m ngày vẫn chưa.

Ví dụ:

Nhập	In ra
4 5 1 2 3 4 1 2 2 3 1 4	4

Kiểm tra: nhập

6 7
1 2
3 4
5 6
1 3
2 4
4 5
1 6

Xem đáp số

6

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 11. Thời điểm cả lớp quen nhau

Lớp có n bạn. Có m sự kiện, sự kiện thứ i xảy ra lúc t_i: hai bạn u_i, v_i làm quen. Các sự kiện được cho không theo thứ tự thời gian. Bạn của bạn coi là quen. Dòng đầu có n, m (2 ≤ n ≤ 10⁵, 1 ≤ m ≤ 2 × 10⁵), m dòng sau mỗi dòng có t, u, v (1 ≤ t ≤ 10⁹). In ra thời điểm sớm nhất mà cả lớp quen nhau, hoặc -1.

Ví dụ:

Nhập	In ra
4 4 20 1 2 5 3 4 12 2 3 30 1 4	20

Kiểm tra: nhập

6 6
50 1 2
10 3 4
70 5 6
20 2 3
90 4 5
40 1 6

Xem đáp số

70

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 12. Phá đường

Có n thành phố và m con đường. Lần lượt phá từng con đường theo một thứ tự cho trước cho đến khi hết. Dòng đầu có n, m (1 ≤ n ≤ 10⁵, 1 ≤ m ≤ 2 × 10⁵), m dòng sau mỗi dòng có u, v (con đường thứ i), dòng cuối có m số: thứ tự phá (một hoán vị của 1, …, m). Sau mỗi lần phá, in ra số nhóm thành phố đi được tới nhau (cách nhau dấu cách).

Ví dụ:

Nhập	In ra
4 4 1 2 2 3 3 4 4 1 2 4 1 3	1 2 3 4

Kiểm tra: nhập

6 6
1 2
2 3
3 1
4 5
5 6
1 4
6 3 1 4 2 5

Xem đáp số

2 2 3 4 5 6

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 13. Đếm cặp đi được với tải trọng giới hạn

Có n thành phố và m con đường, đường thứ i nối u_i, v_i và có độ dốc w_i. Một chiếc xe chỉ leo được dốc không quá x, nên chỉ đi được trên các đường có w ≤ x. Dòng đầu có n, m, q (1 ≤ n ≤ 10⁵, 0 ≤ m, q ≤ 10⁵), m dòng sau mỗi dòng có u, v, w (1 ≤ w ≤ 10⁹), q dòng sau mỗi dòng có x. Với mỗi x, in ra số cặp thành phố (không kể thứ tự) đi được tới nhau chỉ dùng các đường có w ≤ x.

Ví dụ:

Nhập	In ra
5 4 3 1 2 3 2 3 7 4 5 2 3 4 5 2 5 10	1 4 10

Kiểm tra: nhập

7 6 4
1 2 10
2 3 20
4 5 5
5 6 15
6 7 25
3 4 30
4
15
25
30

Xem đáp số

0
4
9
21

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 4. Ràng buộc giữa các phần tử

Bài 14. Bằng nhau và khác nhau

Có n biến x₁, …, x_n và m ràng buộc, mỗi ràng buộc là u = v hoặc u != v (x_u bằng hoặc khác x_v). Dòng đầu có n, m (1 ≤ n ≤ 10⁵, 1 ≤ m ≤ 2 × 10⁵), m dòng sau mỗi dòng có u, ký hiệu (= hoặc !=), v. In ra YES nếu gán được giá trị cho các biến thỏa mọi ràng buộc, ngược lại NO.

Ví dụ:

Nhập	In ra
4 4 1 = 2 2 = 3 3 != 4 1 != 3	NO

Kiểm tra: nhập

6 6
1 = 2
3 = 4
5 != 6
2 != 3
6 = 1
4 = 5

Xem đáp số

YES

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 15. Chia hai đội

Có n bạn cần chia thành hai đội. Lần lượt có m yêu cầu, mỗi yêu cầu là u v: u và v phải ở khác đội. Dòng đầu có n, m (1 ≤ n ≤ 10⁵, 1 ≤ m ≤ 2 × 10⁵), m dòng sau mỗi dòng có u, v. In ra số thứ tự (từ 1) của yêu cầu đầu tiên làm cho không thể chia đội thỏa mọi yêu cầu đã có, hoặc 0 nếu luôn chia được.

Ví dụ:

Nhập	In ra
4 4 1 2 2 3 3 4 1 3	4

Kiểm tra: nhập

6 6
1 2
3 4
5 6
2 3
4 5
6 1

Xem đáp số

0

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 16. Chênh lệch cân nặng

Có n hộp. Có m thông tin, mỗi thông tin u v d nghĩa là hộp v nặng hơn hộp u đúng d (d có thể âm); các thông tin không mâu thuẫn nhau. Sau đó có q câu hỏi u v. Dòng đầu có n, m, q (1 ≤ n ≤ 10⁵, 0 ≤ m, q ≤ 10⁵), |d| ≤ 10⁶. Với mỗi câu hỏi, in ra (cân nặng hộp v) - (cân nặng hộp u) nếu suy ra được, ngược lại in ra ?.

Ví dụ:

Nhập	In ra
4 2 3 1 2 5 2 3 -2 1 3 3 1 1 4	3 -3 ?

Kiểm tra: nhập

6 4 4
1 2 10
3 2 4
4 5 -7
6 4 1
1 3
5 6
1 5
2 2

Xem đáp số

6
6
?
0

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 5. DSU tìm chỗ trống

Bài 17. Bãi đỗ xe

Bãi đỗ xe có n chỗ đánh số 1 đến n xếp thành vòng tròn. Lần lượt có n xe vào, xe thứ i muốn đỗ chỗ p_i; nếu chỗ đó đã có xe thì đi tiếp sang chỗ p_i + 1, p_i + 2, … (sau chỗ n là chỗ 1) và đỗ ở chỗ trống đầu tiên. Dòng đầu có n (1 ≤ n ≤ 2 × 10⁵), dòng thứ hai có n số p_i. In ra chỗ đỗ của từng xe.

Ví dụ:

Nhập	In ra
5 2 2 5 5 2	2 3 5 1 4

Kiểm tra: nhập

8
3 3 3 8 8 1 2 3

Xem đáp số

3 4 5 8 1 2 6 7

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 18. Sơn tường

Bức tường có n ô, ban đầu chưa sơn. Lần lượt có m lần sơn, lần thứ i sơn mọi ô từ l_i đến r_i bằng màu c_i (sơn đè lên màu cũ). Dòng đầu có n, m (1 ≤ n, m ≤ 2 × 10⁵), m dòng sau mỗi dòng có l, r, c (1 ≤ c ≤ 10⁹). In ra màu cuối cùng của từng ô, ô chưa sơn in 0.

Ví dụ:

Nhập	In ra
8 3 1 5 2 3 7 9 2 3 4	2 4 4 9 9 9 9 0

Kiểm tra: nhập

10 4
1 10 1
4 6 2
2 8 3
5 5 4

Xem đáp số

1 3 3 3 4 3 3 3 1 1

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 6. Gộp thêm thông tin

Bài 19. Số màu trong nhóm

Có n người, người thứ i mặc áo màu c_i. Dòng đầu có n, q (1 ≤ n, q ≤ 10⁵), dòng thứ hai có n số c_i (1 ≤ c_i ≤ 10⁹), q dòng sau mỗi dòng là 1 u v (u và v vào cùng nhóm) hoặc 2 x (hỏi nhóm của x có bao nhiêu màu áo khác nhau). Với mỗi câu hỏi loại 2, in ra đáp số.

Ví dụ:

Nhập	In ra
5 6 1 2 1 3 2 2 1 1 1 2 1 3 1 2 3 1 4 5 2 5	1 2 2

Kiểm tra: nhập

8 8
5 5 7 9 7 5 2 9
1 1 2
2 2
1 3 4
1 2 3
2 1
1 6 7
1 8 6
2 7

Xem đáp số

1
3
3

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 20. Nước dâng

Bản đồ là bảng m hàng, n cột, ô (r, c) có độ cao h. Khi mực nước là x, các ô có độ cao lớn hơn x còn khô; hai ô khô chung cạnh thuộc cùng một vùng. Dòng đầu có m, n, q (1 ≤ m, n ≤ 500, 1 ≤ q ≤ 10⁵), m dòng sau mỗi dòng có n số h (0 ≤ h ≤ 10⁹), q dòng sau mỗi dòng có một mực nước x. Với mỗi x, in ra số vùng khô.

Ví dụ:

Nhập	In ra
3 3 3 1 5 2 4 3 6 2 7 1 0 2 4	1 1 3

Kiểm tra: nhập

4 4 4
5 1 5 1
1 5 1 5
9 9 2 8
3 7 6 4
0
1
4
7

Xem đáp số

1
3
4
2

Hướng dẫn giải chi tiết: liên hệ tác giả.

Lời giải chi tiết các bài luyện tập

Đáp số của từng bài ở ngay dưới đề để các bạn tự kiểm tra. Lời giải chi tiết (phân tích, chạy tay, chương trình Python và C++, lưu ý khi làm bài) có trong bộ tài liệu có phí của chuyên đề.

Thầy cô và các bạn muốn mua bộ tài liệu vui lòng liên hệ tác giả qua Zalo 0972465159 hoặc Facebook.