陈维晃的个人主页

最近做了一些并查集的题目，所以在这里整理一些笔记。
并查集是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。常常在使用中以森林来表示。用树的根节点来区分是否处于不同集合。对于每个节点只需要记录其父节点的编号即可。
如建立int pre[]数组表示树结构，下图在数组中的表示为
pre[1]=3;pre[2]=1;pre[3]=3;pre[4]=3;pre[5]=3;pre[6]=1;

所有的节点都指向其父节点，只有根节点是指向自身。

一.并查集的主要操作：

1.1 判断两个元素是否属于相同的集合

需要注意的是，在初始状态我们认为每个元素都是一个独立的集合，既pre[i]=i;
要判断两个元素是否属于相同的集合，只要找到其根节点就可以，不同的集合属于不同的树，自然根节点也就不同了。查找根节点只要判断pre[x]是否等于x即可。

C语言代码表示形式

int Find(int x)
{
  while(x!=pre[x]) x=pre[x];
  return x;
}

1.2 合并两个不同集合

因为每个节点只记录其父节点的编号，所以只要将其中一棵树的根节点指向另一棵树的根节点（其实可以指向另一棵树的任何一个节点）。

C语言代码表示形式

void Union(int a,int b)
{
  a=Find(a);
  b=Find(b);
  pre[b]=a;
}

二.并查集的优化

2.1 路径压缩

并查集的一棵树有可能像左边的那个图一样么？

情况可能会更糟，当一棵树完全退化成一条链的时候对于Find操作是非常不利的。所以我们通常的做法是在Find操作的时候将所查找的元素所在链上的元素都指向根节点，使这棵树变得像右边那样，这样下次再查早这条链上的元素是就可以省下非常多的操作。

C语言代码表示形式

int Find(int x)
{
  int t,r=x;
  while(x!=pre[x]) x=pre[x];
  while(r!=x)
    {
      t=pre[r];
      pre[r]=x;
      r=t;
    }
  return x;
}

2.2 Rank合并

除了路径压缩，另一种比较有效的优化手段是，将元素少的集合并到元素多的集合上，这样可以尽可能避免树往链退化。当然这种优化需要一个Rank数组记录每个集合的元素个数。初始状态每个集合的元素个数都是1，当然你也可以全都赋值为0，这里我们需要的只是不同集合之间元素个数的大小关系，而不是确切的值。

C语言代码表示形式

void Union(int a,int b)
{
  a=Find(a);
  b=Find(b);
  if(Rank[a]>=Rank[b])
    {
      pre[b]=a;
      Rank[a]+=Rank[b];
    }
  else
    {
      pre[a]=b;
      Rank[b]+=Rank[a];
    }
}

三.例题

HDU1232
题意：中文的就不多说了，其实就是求一共有多少个不同集合，在添加一些边使这些集合可以连成树。集合个数-1就是我们要添加的边的数量了。

#include 
int pre[1005],Rank[1005];
void Init(int n) /* 初始化函数 */
{
  int i;
  for(i=1;i<=n;i++)
    {
      pre[i]=i;
      Rank[i]=1;
    }
}
int Find(int x)
{
  int t,r=x;
  while(x!=pre[x]) x=pre[x];
  while(r!=x)
    {
      t=pre[r];
      pre[r]=x;
      r=t;
    }
  return x;
}
void Union(int a,int b)
{
  a=Find(a);
  b=Find(b);
  if(a==b) return;
  if(Rank[a]>=Rank[b])
    {
      pre[b]=a;
      Rank[a]+=Rank[b];
    }
  else
    {
      pre[a]=b;
      Rank[b]+=Rank[a];
    }
}
int main()
{
  int i,n,m,a,b,cnt;
  while(scanf("%d",&n)!=EOF)
    {
      if(n==0) return 0;
      Init(n);
      scanf("%d",&m);
      while(m--)
	{
	  scanf("%d%d",&a,&b);
	  Union(a,b);
	}
      cnt=0;
      for(i=1;i<=n;i++)
	if(pre[i]==i) ++cnt; /* 记录有多少个根节点 */
      printf("%dn",cnt-1); /* 根节点数减1就是答案了 */
    }
}

并查集另一个非常重要的用处是在Kruskal算法求最小生成树的过程中判定两个点是否处于同一个连通分量（保证不形成圈），从而确定所选的边是否为安全边。