C++ USES map to realize and check the set

  • 2020-10-23 20:14:44
  • OfStack

Syndication set (ES1en-ES2en) is a tree-type data structure used to deal with merging and querying of disjoint sets (Disjoint Sets). There are two operations (1.Union union 2.finddeputy search for representative nodes) and one question to be answered (whether issameset is in a set, or whether there is the same representative node).

Using map implementation mainly through two map objects, one map < data,data > Types of fathermap keyword as child nodes, value of its parent node (nodes not 1 is on behalf of the parent), when we need to find whether the two elements in one set, only 1 straight upward finddupty (function), in the process of looking for, will compress path, hang a route node directly under its representative nodes, see if there is a common representative of the node;

1 map < data,int > Types of sizemap key as node, value for his son the number of nodes (the number applies only to on behalf of the node, a node is invalid), the main use is the merger (union) hang nodes less on behalf of the child in the child nodes represent more representative, and corresponds to the parent node in sizemap value with less on behalf of the child nodes of node number.

The code is as follows:


#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;   
  }
 }
 
// Look for the representative node and compress the path 
 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;
};

Thank you for reading and you are welcome to point out the mistakes!


Related articles: