【算法教程】【C/C++】并查集——程序设计思路与代码实现

faryou1个月前 (09-01)技术教程

前言

        图论是算法中的一个重要内容,图的范围很广,包括二叉树、树、图等。今天我们来学习树的重要内容——并查集。


程序设计思路

        并查集是一个森林(由一棵或多棵树组成的集)。我们可以利用其特性进行一些操作。

        在并查集中,最重要的操作便是并和查。

        并是指将两棵树合并为一棵。这很好进行,因为并查集里的每个数都有一个指针指向自己的父亲。

        查找也不难,只需要一个递归程序,不断查找父亲的父亲,最后找到最老的祖先再返回(注意:并查集中最老的祖先的祖先是其自身)。

        比较重要的是一个优化方案——路径压缩。由于查找是递归调用,故当要找的祖先过于遥远时,我们可以使用路径压缩,将一棵树中的全部非根节点的祖先直接设置为最老的祖先。路径压缩通常在执行查找命令时进行。


代码实现

        下面通过并查集的模板题讲解其用法:

IMG_20240823_204300.png

        这题要求我们模拟并查集的操作,直接上代码:

#include <bits/stdc++.h>
using namespace std;

int n,m,z[200005],x[200005],y[200005],bin[10005];//z、x、y如题意,bin为并查集中每个数的祖先(父亲)

int find(int a){//查找操作
	int x=a;
	if(bin[x]!=x) return bin[x]=find(bin[x]);//在查找的过程中路径压缩
	else return x;//当查到某个数的祖先是它自己时,说明找到了祖先,开始返回
}
void join(int b,int c){//并操作
	if(find(b)!=find(c)) bin[find(b)]=find(c);
}

int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) bin[i]=i;
	for(int i=1;i<=m;i++) scanf("%d%d%d",&z[i],&x[i],&y[i]);
	for(int i=1;i<=m;i++){
		if(z[i]==1) join(x[i],y[i]);
		else{
			if(find(x[i])==find(y[i])) printf("Y\n");
			else printf("N\n");
		}
	}
	return 0;
}

        这样,我们就较好的模拟了一个并查集。


结语

        并查集是图论中较为简单的一科,只需要记下并、查两个操作就可以解决相关问题。我是faryou,再见!

本文链接:https://blog.faryou.eu.org/post/96.html 转载需经作者授权!

分享到:

扫描二维码推送至手机访问。

版权声明:本文由faryou的博客发布,如需转载请注明出处。

本文链接:https://blog.faryou.eu.org/post/96.html

标签: C++算法基础
分享给朋友:

发表评论

访客

◎欢迎参与讨论,请在这里发表您的看法和观点。