Disjoint Sets

Nguồn: TopCoder
Người dịch: T

Disjoint Sets là cấu trúc dữ liệu hữu ích được sử dụng thường xuyên trong các cuộc thi, từ VOI (Vietnam Olympiad Informatics) đến IOI (International Informatics Olympiad). Bài viết này sẽ đưa ra các cách cài đặt Disjoint Sets hiệu quả và nhanh nhất.

Bài toán

Mở đầu, ta hãy xét bài toán sau:

Trong một phòng có

$N$ người, ta định nghĩa hai người là bạn nếu họ là bạn bè trực tiếp của nhau hoặc gián tiếp là bạn của nhau. Bạn gián tiếp có nghĩa là nếu

$A$ là bạn với

$B$, và

$B$ là bạn với

$C$, thì

$A$ cũng là bạn với

$C$. Một nhóm bạn là một nhóm mà hai người bất kỳ trong nhóm là bạn. Đưa ra danh sách những người là bạn bè trực tiếp với nhau, hãy tìm số nhóm bạn và số người trong mỗi nhóm.

Ví dụ

Với

$N=5$ và danh sách bạn bè là:

$1-2$,

$5-4$, và

$5-1$. Đây là hình của đồ thị đại diện cho các nhóm bạn.

$1$ và

$2$ là bạn, sau đó

$5$ và

$4$ là bạn, cuối cùng

$5$ và

$1$ là bạn, nhưng

$1$ là bạn với

$2$; do đó

$5$ và

$2$ là bạn bè, v.v.

Cuối cùng ta có

$2$ nhóm bạn: một nhóm là

$\{1,2,4,5\}$, và nhóm còn lại là

$\{3\}$.

Ý tưởng

Đầu tiên, Disjoint Sets là một cấu trúc dữ liệu quản lý các tập hợp không giao nhau, chứa các tập hợp không giao nhau

$S_1$,

$S_2$,

$S_3$, …,

$S_n$. Hai tập hợp không giao nhau nếu giao của chúng là tập hợp rỗng. Trong cấu trúc dữ liệu Disjoint Sets, mọi tập hợp đều có một đại diện là một phần tử của tập hợp đó. Trong các bài toán, Disjoint Sets có vai trò gộp hai tập hợp rời rạc với nhau.

Hãy xét phương thức hoạt động của Disjoint Sets đối với ví dụ đã cho ở bài toán mở đầu.
Các phần tử sẽ được sắp xếp thành các tập hợp, và đại diện của mỗi tập hợp là giá trị có chỉ số lớn nhất. Lúc đầu có

$5$ tập hợp:

$\{1\}$,

$\{2\}$,

$\{3\}$,

$\{4\}$,

$\{5\}$. Không ai là bạn của bất kỳ ai và mọi người đều là đại diện cho nhóm của chính mình. Bước tiếp theo là

$1$ và

$2$ trở thành bạn bè, điều này có nghĩa là nhóm có

$1$ và nhóm có

$2$ sẽ trở thành một nhóm. Khi đó ta có các nhóm sau:

$\{1,2\},\{3\},\{4\},\{5\}$, trong đó đại diện của nhóm đầu tiên sẽ là

$2$. Tiếp theo,

$5$ và

$4$ trở thành bạn bè. Các nhóm sẽ là

$\{1,2\},\{3\},\{4,5\}$. Cuối cùng

$5$ và

$1$ trở thành bạn bè, và các nhóm sẽ là

$\{1,2,4,5\},\{3\}$. Đại diện của nhóm đầu tiên sẽ là

$5$ và đại diện cho nhóm thứ hai là

$3$. (Ta sẽ xem xét lý do tại sao ta cần các đại diện ở phần sau). Sau cùng thì ta có

$2$ tập hợp, tập hợp đầu tiên có bốn phần tử và tập hợp thứ hai có một phần tử, và đây cũng là câu trả lời cho bài toán ví dụ: hai nhóm, trong đó có một nhóm bốn người và một nhóm một người.

Vậy, làm thế nào để kiểm tra xem hai người có trong cùng một nhóm hay không? Đây là lí do mà ta sử dụng các phần tử đại diện. Giả sử ta muốn kiểm tra xem

$3$ và

$2$ có thuộc cùng một nhóm hay không, ta kiểm tra hai đại diện của các tập hợp chứa

$2$ và

$3$. Nếu đại diện của tập hợp chứa

$3$ giống với đại diện của tập hợp chứa

$2$ thì

$2$ và

$3$ cùng thuộc một nhóm. Ở đây, ta có một đại diện là

$5$ và đại diện còn lại là

$3$; do đó

$2$ và

$3$ không ở trong cùng một nhóm bạn.

Cài đặt

Ta hãy định nghĩa một số thao tác sau:

• create-set(x) - tạo một tập hợp mới với một phần tử
  $\{x\}$.
• merge-sets(x, y) - gộp tập hợp chứa phần tử
  $x$ và tập hợp chứa phần tử
  $y$ (với
  $x$ và
  $y$ nằm trong các tập hợp khác nhau) thành một tập hợp mới. Đồng thời, hai tập hợp ban đầu sẽ bị xóa.
• find-set(x) - trả về đại diện hoặc con trỏ đến đại diện của tập hợp chứa phần tử
  $x$.

Lời giải của bài toán ban đầu đã sử dụng các thao tác trên:

for (int x = 1; x <= n; x++) create-set(x); //với x là từng người
for (int i = 1; i <= m; i++){ //với m là số cặp bạn bè
    x = a[i]; y = b[i]; //với từng cặp bạn (x, y)
    if (find-set(x) != find-set(y)) merge-sets(x, y); 
    //nếu hai bạn chưa cùng một nhóm thì gộp hai nhóm có chứa hai bạn
}

Khi đó, để kiểm tra xem 2 người

$(x,y)$ có trong cùng một nhóm hay không, ta kiểm tra xem liệu (find-set(x)=find-set(y)) hay không.

Cài đặt Disjoint Sets với danh sách liên kết

Một cách để triển khai Disjoint Sets là biểu diễn từng tập hợp bằng một danh sách liên kết. Danh sách liên kết là một cấu trúc dữ liệu trong đó là một danh sách mà mỗi phần tử đều liên kết với phần tử đứng sau nó trong danh sách. Khi cài đặt Disjoint Sets, mỗi đối tượng (phần tử) sẽ nằm trong danh sách liên kết và chứa hai con trỏ. Một con trỏ chỉ đến phần tử tiếp theo trong tập hợp và một con trỏ khác đến đại diện của tập hợp.

Dưới đây là một hình ảnh minh họa cho bài toán ví dụ sau khi tất cả các hoạt động được thực hiện.

Các mũi tên màu xanh là con trỏ đến đại diện tập hợp và các mũi tên màu đen là con trỏ đến phần tử tiếp theo trong tập hợp.

Độ phức tạp thuật toán
Khi biểu diễn các tập hợp với danh sách liên kết, ta xét từng thao tác:

• create-set(x): chỉ tạo một danh sách liên kết mới có phần tử duy nhất là
  $x$, cho độ phức tạp
  $O(1)$
• find-set(x): chỉ trả về con trỏ đến đại diện của tập hợp chứa phần tử
  $x$, cho độ phức tạp
  $O(1)$
• merge-sets(x, y): bằng việc nối danh sách của
  $x$ vào cuối danh sách của
  $y$; trong đó đại diện của tập hợp mới là đại diện của tập hợp ban đầu chứa
  $y$; đồng thời sau đó ta phải cập nhật con trỏ thành đại diện cho từng phần tử ban đầu trong danh sách của
  $x$. Điều này cần thời gian tuyến tính là độ dài của danh sách
  $x$. Trong trường hợp xấu nhất, độ phức tạp sẽ là
  $O(M^2)$, với
  $M$ là số lần lặp lại thao tác.

Như vậy, độ phức tạp thuật toán trung bình là

$O(N)$ cho mỗi vòng lặp tập hợp với

$N$ trung bình số lượng phần tử trong mỗi tập hợp.

Bằng cách sử dụng thuật giải gộp tập có trọng số (weighted-union heuristic), ta có thể hiệu quả hóa thuật toán. Trong trường hợp này, giả sử rằng đại diện của tập hợp đồng thời chứa thông tin về số lượng phần tử trong tập hợp đó. Cách tối ưu hóa thuật toán là luôn nối danh sách ngắn hơn vào danh sách dài hơn, và trong trường hợp bằng nhau, ta sẽ nối tùy ý. Khi đó độ phức tạp của thuật toán là

$O(M+NlogN)$; trong đó

$M$ là số hoạt động của ba thao tác đã đề cập, và

$N$ là số hoạt động create-set. Tuy nhiên, BFS sẽ giải quyết bài toán trong

$O(M+N)$ và bộ nhớ của

$O(N+M)$. Ta có thể thấy rằng ta đã tối ưu hóa bộ nhớ nhưng không tối ưu hóa được thời gian chạy.

Cài đặt Disjoint Sets với cây

Cây là một trong các cấu trúc hữu hiệu nhất dùng để cài đặt Disjoint Sets. Ta sẽ biểu diễn các tập hợp bằng các nút trong cây, với mỗi nút chứa một phần tử và mỗi cây đại diện cho một tập hợp. Mỗi phần tử sẽ chỉ đến gốc của nó và gốc của mỗi cây là đại diện của tập hợp đồng thời là phần tử gốc của chính nó.

Với ví dụ ở bài toán mở đầu, các cây sẽ được mô tả trong từng bước sau
Bước 1: Không ai là bạn của bất kỳ ai

Chúng ta có 5 cây và mỗi cây có một phần tử duy nhất, đó là gốc và là đại diện của cây đó.
Bước 2: 1 và 2 là bạn bè, merge-sets(1, 2):

Thao tác được thực hiện là merge-sets(1, 2). Bây giờ, chúng ta có 4 cây, một cây chứa 2 phần tử và có gốc là 1. Các cây còn lại chỉ có một phần tử duy nhất.
Bước 3: 5 và 4 là bạn bè, merge-sets(5, 4)

Thao tác được thực hiện là merge-sets(5, 4). Bây giờ chúng ta có 3 cây, 2 cây có 2 phần tử và một cây có một phần tử.
Bước 4: 5 và 1 là bạn bè, merge-sets(5, 1)

Thao tác được thực hiện là merge-sets(5, 1). Bây giờ chúng ta có 2 cây, một cây có 4 phần tử và cây còn lại chỉ có một phần tử.

Code C++

int find-set(int x){
    if(parent[x] == x) return x; 
    //nếu x đã duyệt đến gốc (đại diện) của x thì trả kết quả
    else return find-set(parent[x]); 
    //nếu không thì tiếp tục duyệt
}
void merge-sets(int x, int y){
    if((x = find-set(x)) == (y = find-set(y))) return;
    size[x] += size[y]; //gộp các phần tử của tập chứa y vào tập chứa x
    parent[y] = x; //gán gốc của y là x
}

Tuy nhiên, ta có thể thấy rằng, thuật toán này không hiệu quả hơn so với danh sách liên kết. Để tăng tốc thuật toán này, ta sử dụng hai thuật giải heuristics là gộp theo thứ hạng (union by rank) và nén đường dẫn (path compression).

Ý tưởng của “gộp theo thứ hạng” là làm cho gốc của cây có ít nút hơn trỏ đến gốc của cây có nhiều nút hơn. Đối với mỗi nút, ta duy trì một thứ hạng gần đúng với logarit của kích thước cây con và cũng là giới hạn trên về chiều cao của nút. Khi merge-sets(x, y) được gọi, gốc có thứ hạng nhỏ hơn được thực hiện để trỏ đến gốc có thứ hạng lớn hơn.

Ý tưởng của “nén đường dẫn”, được sử dụng cho thao tác find-set(x), là làm cho mỗi nút trên đường dẫn tìm điểm trỏ trực tiếp đến gốc. Điều này sẽ không thay đổi bất kỳ thứ tự cấp bậc nào.

Để cài đặt Disjoint Sets với hai thuật toán trên, ta phải truy vết theo thứ hạng. Với mỗi nút

$x$, ta giữ nguyên giá trị rank[x] (có nghĩa là thứ hạng của

$x$), giá trị này lớn hơn hoặc bằng số cạnh trong đường đi dài nhất giữa nút

$x$ và một nút con. Khi lệnh create-set(x) được gọi, rank[x] ban đầu sẽ bằng 0. Khi một phép toán merge-sets(x, y) được thực hiện thì gốc của thứ hạng cao hơn sẽ trở thành gốc của gốc của thứ hạng thấp hơn - hoặc, trong trường hợp bằng nhau, ta tùy ý chọn một trong hai gốc làm gốc và tăng thứ hạng của nó.

Code C++

int find-set(int x){
    return rank[v] < 0 ? v
            : (rank[v] = find-set(rank[v]));
    //kĩ thuật Path Compression
    //trực tiếp gán lại rank[v] = find-set(rank[v])
}
void merge-sets(int x, int y){
    if((x = find-set(x)) == (y = find-set(y))) return;
    //x và y đã thuộc cùng một nhóm, ta không cần làm gì nữa
    if(rank[x] == rank[y]) {
        rank[x]++;
        rank[y] = x;
        return;
    }
    if(rank[x] > rank[y]) swap(x, y);
    //kĩ thuật Union-by-rank:
    //nếu thứ hạng của nút x cao hơn thứ hạng của nút y thì đổi chỗ x và y
    rank[x] += rank[y];
    rank[y] = x;
}

Độ phức tạp thuật toán
Khi ta chỉ sử dụng "gộp theo thứ hạng" thì thời gian chạy mà ta đã đạt được sẽ chỉ bằng với kỹ thuật "gộp tập có trọng số" khi ta sử dụng danh sách liên kết

Khi ta sử dụng cả “gộp theo thứ hạng” và “nén đường dẫn”, thời gian chạy lâu nhất là

$O(m\alpha (m,n))$, trong đó

$\alpha (m,n)$ là nghịch đảo tăng rất chậm của hàm Ackermann và rất nhỏ so với

$N$.

Như vậy, ta đã có thuật toán với thời gian chạy và bộ nhớ sử dụng được tối ưu.

Trở lại bài toán

Bài toán mở đầu bài viết có thể giải quyết được khi sử dụng Disjoint Sets với độ phức tạp là

$O(N+M)$ và với bộ nhớ

$O(N)$. Sự khác biệt về thời gian chạy là không lớn nếu bài toán được giải quyết bằng BFS, nhưng ta không cần phải ghi nhớ các đỉnh của đồ thị.

Hãy xét bài toán sau: Trong một căn phòng có

$N$ người và

$Q$ truy vấn. Mỗi truy vấn có dạng “

$x$

$y$

$1$”, nghĩa là

$x$ là bạn với

$y$; hoặc “

$x$

$y$

$2$”, nghĩa là yêu cầu trả lời liệu

$x$ và

$y$ có thuộc cùng một nhóm bạn tại thời điểm đó hay không. Trong trường hợp này, lời giải với Disjoint Sets là nhanh nhất, cho độ phức tạp là

$O(N+Q)$.

Luyện tập

Disjoint Sets là một công cụ hữu ích làm nền tảng để sử dụng các thuật toán khác nhau hoặc thậm chí để giải quyết các vấn đề trong SRM. Nó hiệu quả và sử dụng dung lượng bộ nhớ nhỏ. Nó cũng hữu ích với các ứng dụng như “Tìm cây khung nhỏ nhất của đồ thị”, “Chia tập hợp các nguyên tử thành phân tử hoặc đoạn phân tử”, “Ghi nhãn thành phần được kết nối trong phân tích hình ảnh” và các ứng dụng khác.

Một số bài tập từ cơ bản đến nâng cao đã được tổng hợp trên VNOI:

• Thùng nước - Bài cơ bản
• Tag Disjoint Sets
• Cây khung nhỏ nhất

Hy vọng bạn thấy bài viết này hữu ích!

Tham khảo

• Thomas H. Cormen, Introduction to Algorithms
• Wikipedia