#include "stdafx.h"
Status InitUFSet(UFSet* set,int n)
{//初始化并查集
  int i; 
  for( i=0;i<n;i++)
  {
      set[i].parent =-1;/* 開始每個節點單獨構成一個集合 */
      set[i].rank = 0;/* 權值視具體情況付初值 */
  }
  return OK;
}

int UFSetFind(UFSet* set,int x)
{//初始條件：存在并查集set，和要查找的元素x，x一定在某個集合中
//操作結果：返回該元素所屬于的集合
  int i,temp;
  for(i=x;set[i].parent>0;i=set[i].parent);//查找到根i
  /* 壓縮路徑以提高以后檢索效率 */
  while(x!=i)     
  {
      temp=set[x].parent;
      set[x].parent=i;
      x=temp;
  }
  return i;
}


int Union(UFSet* set,int a,int b)
{//初始條件：存在并查集set,集合a,集合b
//操作結果：合并集合a，b
  int fa =UFSetFind(set,a); //a的根結點
  int fb =UFSetFind(set,b); //b的根結點
  if(fa==fb) return 0;
  if(set[fa].parent<=set[fb].parent)
  {
      set[fa].parent+=set[fb].parent;
      set[fb].parent =fa;

  }
  else
  {
      set[fb].parent+=set[fa].parent;
      set[fa].parent =fb;
  }
  return 0;
}