C++맵 을 이용 하여 집합 을 실현 하고 찾 습 니 다.

#include<map>
#include<list>
#include<iostream>
using namespace std;
 
template<typename data>
class Unionfindset{
public:
 void makesets(list<data> nodes)
 {
  fathermap.clear();
  sizemap.clear();
  for(auto node:nodes)
  {
   fathermap[node]=node;
   sizemap[node]=1;   
  }
 }
 
//      ，     
 data findduputy(data node)
 {
  data father=fathermap[node];
  if(father!=node)
  {
   return findduputy(father);
  }
  fathermap[node]=father;
  return father;
 } 
 
 void Union(data a ,data b)
 {
  data ahead=findduputy(a);
  data bhead=findduputy(b);
  if(ahead!=bhead)
  {
   data asize=sizemap[a];
   data bsize=sizemap[b];
   if(asize<bsize)
   {
    fathermap[a]=b;
    sizemap[b]=bsize+asize;
   }
   else 
   {
    fathermap[b]=a;
    sizemap[a]=bsize+asize;
   }  
  }  
 } 
 
 bool issameset(data a,data b)
 {
  return findduputy(a)==findduputy(b);
 }
 
private:
 map<data,data> fathermap;
 map<data,data> sizemap;
};