डिस्जॉइंट सेट मूल रूप से सेट्स का एक समूह है जहां कोई आइटम एक से अधिक सेट में नहीं हो सकता। यह सबसेट्स पर यूनियन और फाइंड ऑपरेशन का समर्थन करता है।
Find(): इसका उपयोग यह पता लगाने के लिए किया जाता है कि कोई विशेष तत्व किस सबसेट में है और उस विशेष सेट के प्रतिनिधि को लौटाता है।
Union(): यह दो अलग-अलग सबसेट्स को एक सिंगल सबसेट में मर्ज करता है और एक सेट का प्रतिनिधि दूसरे का प्रतिनिधि बन जाता है।
फंक्शन और छद्मकोड
Begin मान लें k तत्व है makeset(k): k.parent = k. Find(x): If k.parent == k return k. else return Find(k.parent) Union (a,b): दो सेट a और b को इनपुट के रूप में लें। aroot = Find(a) broot = Find(b) aroot.parent = broot End
उदाहरण
#include <iostream> #include <vector> #include <unordered_map> using namespace std; class DisjointSet { //डिस्जॉइंट सेट को प्रस्तुत करने के लिए unordered_map<int, int> parent; public: void makeSet(vector<int> const &wholeset){ //makeset ऑपरेशन निष्पादित करें for (int i : wholeset) // प्रत्येक आइटम के लिए n डिस्जॉइंट सेट बनाएं (one for each item) parent[i] = i; } int Find(int l) { // जिस सेट में तत्व l है उसका रूट खोजें if (parent[l] == l) // यदि l रूट है return l; return Find(parent[l]); // रूट मिलने तक पैरेंट के लिए रिकर्स करें } void Union(int m, int n) { // दो सबसेट्स m और 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 }; // पूरे सेट के आइटम DisjointSet dis; //DisjointSet क्लास इनिशियलाइज़ करें dis.makeSet(wholeset); // wholeset के आइटम्स का व्यक्तिगत सेट बनाएं dis.Union(7, 6); // 7,6 एक ही सेट में हैं print(wholeset, dis); if (dis.Find(7) == dis.Find(6)) // यदि वे एक ही सेट से संबंधित हैं या नहीं। 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
