डिसजॉइंट सेट मूल रूप से सेट के समूह के रूप में होता है जहां कोई भी आइटम एक से अधिक सेट में नहीं हो सकता है। यह संघ का समर्थन करता है और सबसेट पर संचालन ढूंढता है।
ढूंढें (): इसका उपयोग यह पता लगाने के लिए किया जाता है कि कोई विशेष तत्व किस उपसमुच्चय में है और उस विशेष सेट का प्रतिनिधि देता है।
संघ (): यह दो अलग उपसमुच्चय को एक उपसमुच्चय में मिला देता है और एक समुच्चय का प्रतिनिधि दूसरे का प्रतिनिधि बन जाता है।
कार्य और छद्म कोड
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