素集合データ構造を実装するC++プログラム

互いに素なセットは、基本的に、複数のセットにアイテムを含めることができないセットのグループです。サブセットでのユニオンおよび検索操作をサポートします。

Find（）： これは、特定の要素がどのサブセットに含まれているかを検索し、その特定のセットの代表を返すために使用されます。

Union（）： 2つの異なるサブセットを1つのサブセットにマージし、1つのセットの代表が他のセットの代表になります。

関数と擬似コード

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