thuattoan.dev

Level 2 · Cấu trúc dữ liệu

DSU (Union-Find)

Union by rank/size, path compression.

Độ khó: Trung bình Visualizer tương tác9 bài luyện tập

Ý tưởng chính

Disjoint Set Union quản lý các tập hợp rời nhau, hỗ trợ hợp nhất (union) và kiểm tra cùng tập (find) gần như O(1) với path compression.

Hình dung

Mỗi nhóm bạn có một "trưởng nhóm". Muốn biết hai người có cùng nhóm không, hỏi trưởng nhóm của từng người. Hai nhóm kết thân thì một trưởng nhóm nhận trưởng nhóm kia làm sếp.

Cách hoạt động

  1. 1

    Ban đầu mỗi phần tử tự là một nhóm: parent[x] = x.

  2. 2

    find(x): lần theo parent đến gốc (trưởng nhóm) của x.

  3. 3

    union(a, b): tìm gốc của a và b, nếu khác nhau thì gắn gốc này làm con của gốc kia.

  4. 4

    Tối ưu: nén đường đi (trong find, gắn thẳng các nút lên gốc) và gộp theo kích thước (gắn cây nhỏ vào cây lớn).

Độ phức tạp

Với cả hai tối ưu, mỗi thao tác gần như O(1) (chính xác là O(α(n)), α tăng cực chậm).

Khi nào dùng

Gộp các nhóm dần dần và hỏi hai phần tử có cùng nhóm không: thành phần liên thông, Kruskal, phát hiện chu trình trên đồ thị vô hướng.

Lỗi hay gặp

  • Gắn a vào b (parent[a] = b) thay vì gắn gốc vào gốc — làm hỏng cấu trúc.
  • Không nén đường đi nên cây thành một chuỗi dài, find chậm O(n).
  • DSU không hỗ trợ tách nhóm (xoá cạnh).

Liên hệ thực tế

Ứng dụng thực tế

Kỹ thuật này xuất hiện ở đâu ngoài đời — để bạn có sẵn một hình ảnh cụ thể khi học.

  • Nhóm bạn bè, vòng kết nối

    Hai người có cùng một cộng đồng không? Mỗi lần kết bạn là một phép union, câu hỏi là một phép find.

  • Mạng máy tính được nối dần

    Khi lắp thêm từng dây cáp, kiểm tra ngay hai máy đã thông nhau chưa mà không phải duyệt lại cả mạng.

  • Gán nhãn vùng trong ảnh

    Connected component labeling gộp các điểm ảnh liền kề cùng màu để đếm số vật thể, ví dụ tế bào trong ảnh hiển vi.

  • Gộp hồ sơ trùng lặp

    Các tài khoản chung email hoặc số điện thoại được union lại để nhận ra chúng thuộc cùng một người.

Xem thuật toán chạy

Minh hoạ từng bước

Chạy tự động hoặc đi từng bước; theo dõi hình minh hoạ, lời giải thích, giá trị biến và dòng code tương ứng cùng lúc.

Tự làm

Luyện tập trên Codeforces

Sắp xếp từ dễ đến khó theo rating, mỗi bài kèm tóm tắt đề. Bí thì mở gợi ý — có 3 mức, từ hướng suy nghĩ tới gần lời giải.

  • Rating 1200

    Ice Skating(mở Codeforces trong tab mới)

    Có n đống tuyết trên mặt phẳng. Từ một đống, trượt theo 4 hướng sẽ dừng ở đống tiếp theo cùng hàng hoặc cùng cột. Tìm số đống tuyết ít nhất cần thêm để từ mọi đống tới được mọi đống khác.

    Test mẫu & giải thích
    Input
    2
2 1
1 2
    Output
    1

    2 đống tuyết tại (2,1) và (1,2) không cùng hàng cũng không cùng cột nên không trượt được từ đống này sang đống kia. Thêm 1 đống tại (1,1) (hoặc (2,2)): đống mới cùng hàng với một đống và cùng cột với đống còn lại, nên từ bất kỳ đống nào cũng tới được mọi đống khác. Không thêm đống nào thì không đi được, nên đáp án là 1.

  • Rating 1200

    Coloring a Tree(mở Codeforces trong tab mới)

    Cho cây gốc 1, mọi đỉnh ban đầu màu 0. Mỗi bước chọn đỉnh v và màu x, tô toàn bộ cây con của v màu x. Tìm số bước ít nhất để mỗi đỉnh có màu mục tiêu c_v.

    Test mẫu & giải thích
    Input
    6
1 2 2 1 5
2 1 1 1 1 1
    Output
    3

    Cây gốc 1 có con 2 và 5; con của 2 là 3, 4; con của 5 là 6. Màu mục tiêu: đỉnh 1 màu 2, các đỉnh còn lại màu 1. Bước 1: tô cả cây (cây con của 1) màu 2. Bước 2: tô cây con của 2 (gồm 2, 3, 4) màu 1. Bước 3: tô cây con của 5 (gồm 5, 6) màu 1. Không thể ít hơn: gốc phải được tô màu 2, còn hai nhánh 2 và 5 cần màu 1 mà không có cây con nào chứa cả hai nhánh ngoại trừ cây của gốc. Đáp án 3.

  • Rating 1200

    Mahmoud and Ehab and the message(mở Codeforces trong tab mới)

    Có n từ, mỗi từ có chi phí gửi, chia thành k nhóm đồng nghĩa. Thông điệp gồm m từ, mỗi từ có thể thay bằng từ đồng nghĩa. Tìm chi phí gửi nhỏ nhất.

    Test mẫu & giải thích
    Input
    5 4 4
i loser am the second
100 1 1 5 10
1 1
1 3
2 2 5
1 4
i am the second
    Output
    107

    5 từ với chi phí [100,1,1,5,10] chia 4 nhóm đồng nghĩa: {i}, {am}, {loser,second}, {the}. Với thông điệp 'i am the second', chọn từ rẻ nhất trong nhóm của mỗi từ: 'i' chỉ có mình nó → 100; 'am' chỉ có mình nó → 1; 'the' chỉ có mình nó → 5; 'second' cùng nhóm với 'loser' (chi phí 1, rẻ hơn chi phí 10 của chính nó) nên thay bằng 'loser' → 1. Tổng chi phí = 100+1+5+1 = 107.

  • Rating 1300

    Books Exchange (hard version)(mở Codeforces trong tab mới)

    Có n đứa trẻ, mỗi đứa có một cuốn sách; mỗi ngày đứa i đưa sách của mình cho đứa p_i (p là hoán vị). Với mỗi đứa, tìm ngày đầu tiên cuốn sách của nó quay lại (n ≤ 2·10⁵).

    Test mẫu & giải thích
    Input
    6
5
1 2 3 4 5
3
2 3 1
6
4 6 2 1 5 3
1
1
4
3 4 1 2
5
5 1 2 4 3
    Output
    1 1 1 1 1 
3 3 3 
2 3 3 2 1 3 
1 
2 2 2 2 
4 4 4 1 4

    1. Test 1

      Vì p là hoán vị, sách của đứa i quay lại đúng sau số ngày bằng độ dài chu trình chứa i trong p. Ở test thứ 2: n=3, p=[2,3,1] tạo một chu trình duy nhất độ dài 3 (1→2→3→1), nên cả 3 đứa đều nhận kết quả 3, khớp '3 3 3'.

    2. Test 2

      Ở test thứ 3: n=6, p=[4,6,2,1,5,3] tách thành chu trình (1,4) độ dài 2, chu trình (2,6,3) độ dài 3 và chu trình (5) độ dài 1; đáp án của mỗi đỉnh chính là độ dài chu trình chứa nó, cho kết quả '2 3 3 2 1 3'.

  • Rating 1400

    News Distribution(mở Codeforces trong tab mới)

    Có n người dùng và m nhóm bạn. Tin tức lan từ người biết tới mọi người chung nhóm. Với mỗi người x, đếm số người sẽ biết tin nếu x là người bắt đầu lan tin.

    Test mẫu & giải thích
    Input
    7 5
3 2 5 4
0
2 1 2
1 1
2 6 7
    Output
    4 4 1 4 4 2 2

    n=7 người, các nhóm khác rỗng là {2,5,4} (size 3), {1,2} (size 2), {6,7} (size 2) (nhóm size 0 bỏ qua, nhóm {1} đơn lẻ không tạo liên kết mới). Gộp các nhóm có chung người: {2,5,4} rồi {1,2} nhập chung vì có phần tử 2 chung, tạo thành {1,2,4,5} kích thước 4; {6,7} kích thước 2 đứng riêng; người 3 không thuộc nhóm nào nên đứng một mình (kích thước 1). Đáp án mỗi người là kích thước thành phần chứa họ: người 1,2,4,5 → 4; người 3 → 1; người 6,7 → 2, khớp '4 4 1 4 4 2 2'.

  • Rating 1600

    Socks(mở Codeforces trong tab mới)

    Có n chiếc tất với k màu, và m ngày; ngày i phải đi tất l_i và r_i, hai chiếc phải cùng màu. Tìm số chiếc tất ít nhất cần sơn lại màu.

    Test mẫu & giải thích
    Input
    3 2 3
1 2 3
1 2
2 3
    Output
    2

    n=3 tất màu ban đầu [1,2,3], 2 ngày yêu cầu đôi (1,2) và (2,3) cùng màu. Hai ràng buộc nối chung qua tất số 2 nên tất 1,2,3 buộc phải cùng một màu, tức là một thành phần liên thông kích thước 3. Trong thành phần này mỗi màu 1, 2, 3 chỉ xuất hiện đúng 1 lần nên tần suất lớn nhất là 1; giữ nguyên đúng 1 chiếc mang màu đó và phải sơn lại 3−1 = 2 chiếc còn lại, khớp sampleOutput = 2.

  • Rating 1800

    Vessels(mở Codeforces trong tab mới)

    Có n bình xếp chồng từ trên xuống, bình i chứa tối đa a_i lít; nước tràn khỏi bình i chảy xuống bình i + 1 (tràn khỏi bình cuối thì mất). Xử lý truy vấn: đổ x lít vào bình p, hoặc hỏi bình k đang có bao nhiêu nước.

    Test mẫu & giải thích
    Input
    2
5 10
6
1 1 4
2 1
1 2 5
1 1 4
2 1
2 2
    Output
    4
5
8

    2 bình có cap [5,10]. Đổ 4 lít vào bình 1 (chưa đầy, còn dư 1) rồi hỏi bình 1 → 4, khớp dòng đầu. Đổ tiếp 5 lít vào bình 2 (đang rỗng, còn dư 5, chưa đầy). Đổ thêm 4 lít vào bình 1: bình 1 đang có 4+4=8 > cap 5 nên đầy ở mức 5, phần tràn 3 lít chảy xuống bình 2, bình 2 = 5+3 = 8 (chưa vượt cap 10). Hỏi bình 1 → 5 (dòng 2); hỏi bình 2 → 8 (dòng 3).

  • Rating 1900

    Roads not only in Berland(mở Codeforces trong tab mới)

    Có n thành phố và n − 1 con đường. Mỗi ngày được phá một con đường và xây một con đường mới. Tìm số ngày ít nhất để mọi thành phố đi được tới nhau và in kế hoạch.

    Test mẫu & giải thích
    Input
    2
1 2
    Output
    0

    n=2 với đúng 1 con đường '1 2' nối 2 thành phố — đây đã là n−1=1 cạnh tạo thành cây khung liên thông đầy đủ, mọi thành phố đã tới được nhau. Do đó không cần phá hay xây thêm con đường nào, số ngày tối thiểu là 0.

  • Rating 1900

    Restructuring Company(mở Codeforces trong tab mới)

    Có n nhân viên, mỗi người ở một phòng riêng. Ba loại truy vấn: gộp phòng của x và y; gộp mọi phòng của x, x+1, …, y; hỏi x và y có cùng phòng không.

    Test mẫu & giải thích
    Input
    8 6
3 2 5
1 2 5
3 2 5
2 4 7
2 1 2
3 1 7
    Output
    NO
YES
YES

    8 nhân viên, ban đầu mỗi người ở phòng riêng. Truy vấn '3 2 5' hỏi 2 và 5 cùng phòng: chưa gộp gì nên NO. '1 2 5' gộp phòng của 2 và 5. Truy vấn '3 2 5' lặp lại: nay cùng phòng → YES. '2 4 7' gộp toàn bộ phòng nhân viên 4..7 thành một, kéo theo 5 (đang ở nhóm {2,5}) nhập chung, tạo nhóm {2,4,5,6,7}. '2 1 2' gộp nhân viên 1..2, vì 2 đang thuộc nhóm trên nên 1 cũng nhập vào, tạo nhóm {1,2,4,5,6,7}. Truy vấn cuối '3 1 7' hỏi 1 và 7: cả hai đều trong nhóm vừa gộp → YES, khớp 'NO YES YES'.