【算法】——并查集
作者：指针不指南吗
专栏：算法篇🐾或许会很慢，但是不可以停下🐾
文章目录
- 1.思想
- 2.模板
- 3.应用
- 3.1 合并集合
- 3.2 连通块中点的数量
1.思想
并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题（即所谓的并、查）
比如说，我们可以用并查集来判断 某个节点是否属于某棵树等。
-
并查集
-
将两个集合合并
-
询问两个元素是否在一个集合当中
-
-
基本原理
每个集合用一棵树来表示。
树根的编号就是整个集合的编号。
每个节点存储它的父节点，p[x]表示x的父节点。
-
相关问题
-
如何判断树根：
if(p[x]==x) -
如何求x的集合编号：
while(p[x]!=x) x=p[x] -
判断两个元素是否在一个集合里面，即两个元素的编号相同：
find(p[x])==find(p[y]) -
如何合并两个集合：px是x的集合编号，py是y的集合编号。
p[x]=y，即让一个集合 a 的根节点指向另一个集合 b 的根节点，把a直接插在b的根节点下面。
-
-
优化
- 路径压缩：让每个节点都直接指向根节点（祖先）
2.模板
并查集的类型模板这里给出三种，具体题目具体分析，看看需要维护什么，添加什么。
(1)朴素并查集：
int p[N]; //存储每个点的祖宗节点// 返回x的祖宗节点
int find(int x)
{if (p[x] != x) p[x] = find(p[x]);return p[x];
}// 初始化，假定节点编号是1~n
for (int i = 1; i <= n; i ++ ) p[i] = i; //初始化每个元素的父节点和祖宗节点就是它本身// 合并a和 b所在的两个集合：
p[find(a)] = find(b); //让a的祖宗节点指向b的祖宗节点，a树插在b根节点下面
(2)维护size的并查集：
int p[N], size[N];
//p[]存储每个点的祖宗节点, size[]只有祖宗节点的有意义，表示祖宗节点所在集合中的点的数量// 返回x的祖宗节点
int find(int x)
{if (p[x] != x) p[x] = find(p[x]);return p[x];
}// 初始化，假定节点编号是1~n
for (int i = 1; i <= n; i ++ )
{p[i] = i;size[i] = 1; //初始化，每个集合里面只有一个元素
}// 合并a和b所在的两个集合：
size[find(b)] += size[find(a)]; //集合大小相加
p[find(a)] = find(b);
(3)维护到祖宗节点距离的并查集：
int p[N], d[N];
//p[]存储每个点的祖宗节点, d[x]存储x到p[x]的距离// 返回x的祖宗节点
int find(int x)
{if (p[x] != x){int u = find(p[x]);d[x] += d[p[x]];p[x] = u;}return p[x];
}// 初始化，假定节点编号是1~n
for (int i = 1; i <= n; i ++ )
{p[i] = i;d[i] = 0;
}// 合并a和b所在的两个集合：
p[find(a)] = find(b);
d[find(a)] = distance; // 根据具体问题，初始化find(a)的偏移量
3.应用
3.1 合并集合
一共有 n 个数，编号是 1∼n，最开始每个数各自在一个集合中。
现在要进行 m 个操作，操作共有两种：
M a b，将编号为 a 和 b 的两个数所在的集合合并，如果两个数已经在同一个集合中，则忽略这个操作；Q a b，询问编号为 a 和 b 的两个数是否在同一个集合中；输入格式
第一行输入整数 n 和 m。
接下来 m 行，每行包含一个操作指令，指令为
M a b或Q a b中的一种。输出格式
对于每个询问指令
Q a b，都要输出一个结果，如果 a 和 b 在同一集合内，则输出Yes，否则输出No。每个结果占一行。
数据范围
1≤n,m≤10510^5105
输入样例：
4 5 M 1 2 M 3 4 Q 1 2 Q 1 3 Q 3 4输出样例：
Yes No Yes
-
代码实现
#includeusing namespace std;const int N=100010;int n,m; //n表示点的数量，m表示操作的次数 int p[N]; //存的每个节点的父节点int find(int x) //返回x的祖宗节点+路径压缩 {if(p[x]!=x) p[x]=find(p[x]);return p[x]; }int main() {scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) p[i]=i; //最开始，每个点都各自在一个集合中，so父节点就是他本身；while(m--){char op[2];int a,b;scanf("%s%d %d",op,&a,&b);//合并if(op[0]=='M') p[find(a)]=p[find(b)]; //让a的祖宗节点等于b的祖宗节点，让a的祖宗节点直接插在b祖宗节点下面else{if(find(a)==find(b)) puts("Yes"); //判断是否属于同一个集合else puts("No");} }return 0; }
注意
读入字母M或者是Q的时候，使用字符串op[2],是因为直接用char的话，可能会出现空格换行的问题作物，这种比较保险，记得在后面使用的时候，用op[0],不能直接使用op
puts自动包含换行
3.2 连通块中点的数量
给定一个包含 n 个点（编号为 1∼n）的无向图，初始时图中没有边。
现在要进行 m 个操作，操作共有三种：
C a b，在点 a 和点 b 之间连一条边，a 和 b 可能相等；Q1 a b，询问点 a 和点 b 是否在同一个连通块中，a 和 b 可能相等；Q2 a，询问点 a 所在连通块中点的数量；输入格式
第一行输入整数 n 和 m。
接下来 m 行，每行包含一个操作指令，指令为
C a b，Q1 a b或Q2 a中的一种。输出格式
对于每个询问指令
Q1 a b，如果 a 和 b 在同一个连通块中，则输出Yes，否则输出No。对于每个询问指令
Q2 a，输出一个整数表示点 a 所在连通块中点的数量每个结果占一行。
数据范围
1≤n,m≤10510^5105
输入样例：
5 5 C 1 2 Q1 1 2 Q2 1 C 2 5 Q2 5输出样例：
Yes 2 3
-
思路
-
连通块就是一个点的集合：集合中的点可以相互到达，直接或者是间接都是可以的；
-
这时候我们可以把它类比成一个树，运用并查集，一个点集合，我们可以用一个编号来表示，属于同一个编号，就说明两个点之间可以相互到达，在一个连通块里面；
-
有三个操作：
-
两点之间连一条边，那么这两个点所在集合中的点，都是可以相互到达的，即合成一个连通块，用并查集中的合并操作；
-
判断是否在一个连通块，用并查集的查询；
-
询问一个点集合的数量，需要我们额外维护，初始化的时候每个集合1个，合并的时候，两个集合数量相加，最后输出即可
-
-
-
代码实现
#includeusing namespace std;const int N=1000010; int n,m; int p[N],sizel[N]; //p表示父节点，sizel表示集合的大小，记住sizel里面放的是祖宗节点，后面容易出错int find(int n) //返回祖宗节点 {if(p[n]!=n) p[n]=find(p[n]);return p[n]; }int main() {scanf("%d%d",&n,&m); //读入点的数量和操作的次数for(int i=1;i<=n;i++){ //初始化，父节点就是它本身；集合大小都是1，只有他自己p[i]=i;sizel[i]=1;}char op[5]; while(m--){scanf("%s",op); //读入操作的名字if(op[0]=='C'){ //合并int a,b;scanf("%d%d",&a,&b);if(find(a)==find(b)) continue; //相同则进入下个循环else{ //不同即操作，两步的顺序不能反！！！sizel[find(b)]+=sizel[find(a)]; //b的集合大小加上a的集合大小p[find(a)]=find(b); //让a的祖宗节点指向b的祖宗节点}}else if(op[1]=='1'){ //查询是否一个集合int a,b;scanf("%d%d",&a,&b);if(find(a)==find(b)) puts("Yes");else puts("No");}else{if(op[1]=='2') { //输出集合大小int d;scanf("%d",&d);printf("%d\n",sizel[find(d)]); }}}return 0; }
