Tag Archives: 并查集

并查集笔记

最近做了一些并查集的题目,所以在这里整理一些笔记。
并查集是一种树型的数据结构,用于处理一些不相交集合(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 路径压缩

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

......

Read more »