ডিসজয়েন্ট সেট মূলত সেটের গোষ্ঠী হিসাবে যেখানে কোনও আইটেম একাধিক সেটে থাকতে পারে না। এটি সাবসেটগুলিতে ইউনিয়ন এবং অনুসন্ধান অপারেশন সমর্থন করে৷
খুঁজে নিন(): এটি একটি নির্দিষ্ট উপাদান কোন উপসেটে আছে তা খুঁজে বের করতে ব্যবহৃত হয় এবং সেই নির্দিষ্ট সেটের প্রতিনিধিকে ফেরত দেয়।
ইউনিয়ন(): এটি দুটি ভিন্ন উপসেটকে একক উপসেটে একত্রিত করে এবং একটি সেটের প্রতিনিধি অন্য সেটের প্রতিনিধি হয়ে ওঠে৷
ফাংশন এবং সিউডোকোড
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
উদাহরণ
#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;
} আউটপুট
6 6 1 2 3 Yes No
