并查集笔记

最近做了一些并查集的题目,所以在这里整理一些笔记。
并查集是一种树型的数据结构,用于处理一些不相交集合(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 <stdio.h>
 
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算法求最小生成树的过程中判定两个点是否处于同一个连通分量(保证不形成圈),从而确定所选的边是否为安全边。

» 本博客采用署名 2.5 中国大陆许可协议进行许可,本文版权归作者所有,欢迎转载,但必须在明显位置给出原文连接。
anyShare分享到:

Leave a Comment

NOTE - You can use these HTML tags and attributes:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>