Giải thuật - Các Cấu Trúc Dữ Liệu cho các Tập Rời Nhau

ª Cấu trúc dữ liệu các tập rời nhau được định nghĩa bởi
– Một tập S của các tập động rời nhau, S = {S1 , S2 ,..., Sk}
° Mỗi tập Si được tượng trưng bởi một phần tử đại diện là một phần tử nào đó của nó.
– Các thao tác
° MAKE-SET(x): tạo một tập mới chỉ gồm x. Vì các tập là rời nhau nên x không được đang nằm trong một tập khác.
° UNION(x, y): tạo tập hội của các tập động Sx và Sy lần lượt chứa x và y, với điều kiện là Sx và Sy là rời nhau.
° FIND-SET(x): trả về một con trỏ chỉ đến phần tử đại diện của tập chứa x.
ª Để cho gọn, sẽ dùng “các tập rời nhau” để gọi “cấu trúc dữ liệu các tập rời nhau”.