c++初级并查集知识点总结

146 阅读 0 评论 97 点赞

我是靠谱客的博主悦耳大神，最近开发中收集的这篇文章主要介绍c++初级并查集知识点总结，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

并查集是一种树型的数据结构，用于处理一些不交集的合并及查询问题。

有一个联合- 查找算法定义了两个用于此数据结构的操作：

Find ：确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。
Union：将两个子集合并成同一个集合。

并查集主要运用在合并元素以及查询两个元素是否在同一集合的问题，在信息学竞赛中广泛涉及

初始化：

一开始，每一个元素都是一个集合，打个比方，每个人所在的 " 家族 " 只有他一个人。我们还需要一个 f 数组，里面存的是他的 “父亲” 的编号，初始值为 f[1]=1,f[2]=2……f[n]=n，如图

2、find函数：find（a）是用来查找a的“祖先”的，例如，我们要查找 a 的祖先，就要去找 a 的父亲的父亲……，直到有个人 b ，他的父亲就是他自己，那么 b 就是 a 的祖先代码如下：int find (int x){ if(f[x] == x) return x;//如果x的父亲就是他自己，则x为a的祖先 else return find (f[x]);//否则a的祖先就是a的父亲的祖先}int x=find(a);find函数：find（a）是用来查找a的“祖先”的，例如，我们要查找 a 的祖先，就要去找 a 的父亲的父亲……，直到有个人 b ，他的父亲就是他自己，那么 b 就是 a 的祖先代码如下：int find (int x){ if(f[x] == x) return x;//如果x的父亲就是他自己，则x为a的祖先 else return find (f[x]);//否则a的祖先就是a的父亲的祖先}int x=find(a);

union函数：

union(a,b) 就是合并 a,b 这两个人所在的家族，只需要把 a的祖先的父亲指向 b的祖先

如何合并？我们设 u=find(a),v=find(b) , 只要将 u,v 其中一个人的父亲编号指向另外一个人就行了，例如 f[u]=v

代码如下：

void Union (int a,int b)//因为union是c++的保留字，所以只好大写u

{

  int u= find(a), v= find(b);//寻找a，b的祖先

  f[u]=v;//合并家族

}

Union (a,b);

在合并的时候还有一个注意点：为什么不能直接把 a 的父亲指向 b ？因为这样并不能合并完全，a 的父亲， a 的父亲的父亲……，都不能合并到 b 的家族里（想一想，为什么？），如图

5、查询两个元素是否在同一集合里：查询 a,b 是否在同一集合里，就是看他们的祖先是否相等，若相等则在同一集合里，否则就不在代码如下：if( find(a) == find(b) ) cout<<"Yn"; //如果祖先相等就输出“Y”else cout<<"Nn"; //否则输出“N”查询两个元素是否在同一集合里：查询 a,b 是否在同一集合里，就是看他们的祖先是否相等，若相等则在同一集合里，否则就不在代码如下：if( find(a) == find(b) ) cout<<"Yn"; //如果祖先相等就输出“Y”else cout<<"Nn"; //否则输出“N”

例题：

至此，你应该对并查集有了初步的了解，是时候上例题了

题目描述

如题，现在有一个并查集，你需要完成合并和查询操作。

输入输出格式

输入格式：

第一行包含两个整数N、M，表示共有N个元素和M个操作。

接下来M行，每行包含三个整数Zi、Xi、Yi

当Zi=1时，将Xi与Yi所在的集合合并

当Zi=2时，输出Xi与Yi是否在同一集合内，是的话输出Y；否则话输出N

输出格式：

如上，对于每一个Zi=2的操作，都有一行输出，每行包含一个大写字母，为Y或者N