现在的位置: 首页 > 综合 > 正文

并查集

2014年03月06日 ⁄ 综合 ⁄ 共 1143字 ⁄ 字号 小 中 大 ⁄ 评论关闭
  1. class UFSet
  2. {
  3.     typedef  struct  UFSetNode
  4.     {
  5.         long  parent;
  6.         long  rank;
  7.     }UFSetNode;   
  8.        
  9. public: 
  10.     
  11.     UFSet(long  sz)
  12.     {
  13.         size = sz;
  14.         
  15.         elem = new UFSetNode[size];
  16.         
  17.         for(long  i = 0; i < size; i++)
  18.         {
  19.             elem[i].parent = -1; 
  20.             elem[i].rank = 0;
  21.         }         
  22.     }
  24.     ~UFSet() { delete [] elem; }
  26.     long  FindSet(long  x)
  27.     {
  28.         long  i, temp;
  30.         for(i = x; elem[i].parent > 0; i = elem[i].parent)
  31.         ;
  33.         while(i != x)
  34.         {
  35.             temp = elem[x].parent;
  36.             elem[x].parent = i;
  37.             x = temp;
  38.         }
  39.         
  40.         return  i;
  41.     }
  43.     void Union(long a, long b)
  44.     {
  45.         long  fa, fb;
  47.         fa = FindSet(a);
  48.         fb = FindSet(b);
  50.         if(fa == fb)
  51.         {
  52.             return;
  53.         }    
  55.         if(elem[fa].parent < elem[fb].parent)
  56.         {
  57.             elem[fa].parent += elem[fb].parent;
  58.             elem[fb].parent = fa;
  59.         }
  60.         else
  61.         {
  62.             elem[fb].parent += elem[fa].parent;
  63.             elem[fa].parent = fb;
  64.         }
  65.     }
  66.     
  67. private:
  68.     
  69.     long        size;
  70.     UFSetNode  *elem;
  71. };  
返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞