并查集的不同写法

#define MAX_SIZE 100005  
int pa[MAX_SIZE];        //存储有向图的边
 
void init()     //初始化 该函数可以根据具体情况保存和初始化需要的内容  
{  
  for(int i = 0; i < MAX_SIZE; i++)  
  {  
    pa[i] = i;  
  } 
}  
 
int find(int a) //不带路劲压缩  
{  
  while(pa[a] != a)  
    a = pa[a];  
  return a;  
}  
 
void merge(int a, int b)      //集合合并  
{  
  int a1 = find(a);  
  int b1 = find(b);
  if(a1 != b1)    //这个判定条件可选，主要是为了防止find路径压缩的时候出现死循环
    pa[a1] = b1;    //如果存的是有向图，并且做题时集合中元素的顺序很重要，不能忽略，那么这里应该用"pa[a] = b;" 
} 

int find(int x)      //找元素所在集合的代表元(因为用了路径压缩，路径压缩的主要目的是为了尽快的确定元素所在的集合）  
{  
  int t1,t2=x;
  while(x!=p[x])  
    x=p[x];  
  while(t2!=p[t2])        //这里优化的思路还是路径压缩（进一步的在查找函数执行的过程中压缩路径)
  {  
    t1=p[t2];  
    p[t2]=x;  
    t2=t1;  
  }  
  return x;  
} 

int find(int x)  
{  
  if(p[x] != x)  
  {         
    int root = find(p[x]);   
    return p[x] = root;  
  }  
  else  
    return x;  
}