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