我的涂鸦圣地

/*
适用范围：集合中元素范围是[1..MAXN]
*/

#include<stdio.h>
#include<memory.h>

#define MAXN 100000
int p[MAXN + 1], r[MAXN + 1];

// 初始化数据结构
void init_set()
{
   memset(p, 0, sizeof(p));
}

// 生成一个新的集合，其中只含有一个元素e
void make_set(int e)
{
   p[e] = e;
   r[e] = 0;
}

// 返回0表示并查森林中找不到该元素
int find_set(int key)
{
   if(key != p[key]) p[key] = find_set(p[key]);
   return p[key];
}

// 合并两个集合s1和s2，以rank大的作为根
void union_set(int s1, int s2)
{
   int p1, p2;
   if(s1 == s2) return;
   p1 = find_set(s1);
   p2 = find_set(s2);
   if(p1 != p2)
   {
       if(r[p1] > r[p2]) p[p2] = p1;
       else if(r[p2] > r[p1]) p[p1] = p2;
       else
       {
           r[p1]++;
           p[p2] = p1;
       }
   }
}

注意,在实现有向树的过程中,合并集合的方法必须是把弧顶节点合并到弧尾节点,就是说,把子节点合并到根节点