Tập hợp rời rạc về cơ bản là một nhóm các tập hợp mà không có mục nào có thể nằm trong nhiều hơn một tập hợp. Nó hỗ trợ kết hợp và tìm hoạt động trên các tập hợp con.
Tìm (): Nó được sử dụng để tìm phần tử cụ thể nằm trong tập hợp con nào và trả về đại diện của tập hợp cụ thể đó.
Union (): Nó hợp nhất hai tập hợp con khác nhau thành một tập hợp con duy nhất và đại diện của một tập hợp này trở thành đại diện của tập hợp khác.
Hàm và mã giả
Begin Assume k is the element makeset(k): k.parent = k. Find(x): If k.parent == k return k. else return Find(k.parent) Union (a,b): Take two set a and b as input. aroot = Find(a) broot = Find(b) aroot.parent = broot End
Ví dụ
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
class DisjointSet { //to represent disjoint set
unordered_map<int, int> parent;
public:
void makeSet(vector<int> const &wholeset){
//perform makeset operation
for (int i : wholeset) // create n disjoint sets
(one for each item)
parent[i] = i;
}
int Find(int l) { // Find the root of the set in which element l belongs
if (parent[l] == l) // if l is root
return l;
return Find(parent[l]); // recurs for parent till we find root
}
void Union(int m, int n) { // perform Union of two subsets m and n
int x = Find(m);
int y = Find(n);
parent[x] = y;
}
};
void print(vector<int> const &universe, DisjointSet &dis) {
for (int i : universe)
cout << dis.Find(i) << " ";
cout << '\n';
}
int main() {
vector<int> wholeset = { 6,7,1,2,3 }; // items of whole set
DisjointSet dis; //initialize DisjointSet class
dis.makeSet(wholeset); // create individual set of the items of wholeset
dis.Union(7, 6); // 7,6 are in same set
print(wholeset, dis);
if (dis.Find(7) == dis.Find(6)) // if they are belong to same set or not.
cout<<"Yes"<<endl;
else
cout<<"No";
if (dis.Find(3) == dis.Find(4))
cout<<"Yes"<<endl;
else
cout<<"No";
return 0;
} Đầu ra
6 6 1 2 3 Yes No