郴州建网站,域名网站电话,企业网站首页效果图,医药行业网站建设参考内容#xff1a; 图论——并查集(详细版) 并查集#xff08;Disjoint-set#xff09;是一种精巧的树形数据结构#xff0c;它主要用于处理一些不相交集合的合并及查询问题。一些常见用途#xff0c;比如求联通子图、求最小生成树的 Kruskal 算法和求最近公共祖先… 参考内容 图论——并查集(详细版) 并查集Disjoint-set是一种精巧的树形数据结构它主要用于处理一些不相交集合的合并及查询问题。一些常见用途比如求联通子图、求最小生成树的 Kruskal 算法和求最近公共祖先LCA等。
并查集的理念是只关注个体属于哪个阵营并不关心这个阵营中个体内部的关系比如我们常说的张三是李家沟的王二是王家坝的。同时并查集借助个体代表集体的思想用一个元素代表整个群体就像我们开学都会有学生代表、教师代表讲话一样在台上讲话的那一个学生就代表了学校所有的学生。
并查集基本操作
并查集的基本操作主要有初始化 init、查询 find和合并 union操作。
初始化
在使用并查集的时候常常使用一个数组fa来存储每个元素的父节点在一开始的时候所有元素与其它元素都没有任何关系即大家相互之间还不认识所以我们把每个元素的父节点设为自己。
#define ARR_LEN 6000int fa[ARR_LEN];void init(int n)
{for(int i 1; i n; i)fa[i] i;
}查询
查询即找到指定元素的祖先。需要注意的是这里我们需要找到指定元素的根祖先不能找到爸爸或者爷爷就停止了而是要找到查找不下去了为止所以要不断的去递归下去直到找到父亲为自己的结点才结束。
int find(int i)
{if(i fa[i]) // 递归出口return i;elsereturn find(fa[i]); // 不断向上查找祖先
}考虑下面的场景假如第一次我们需要查询元素5的祖先第二次需要查询元素4的祖先会发现第一次查询包含了第二次查询的计算过程但我们的程序却傻傻的计算了两次有没有办法去来优化查询过程让每一次查询都能利用到此前查询计算的便利 考虑到并查集并不关心某个元素的爸爸、爷爷是谁只关心最终的祖先是谁所以我们可以在查询的过程中顺便做一些修改比如在查询5的过程中顺便就把4和2的父亲给修改为1即我们在查找过程中进行路经压缩
int find(int i)
{if(i fa[i]){return i;} else {fa[i] find(fa[i]); // 进行路径压缩return fa[i];}
}合并
合并操作即介绍两个人相互认识将他们纳入同一个帮派只需要将俩元素的父亲修改为同一个即可。
void union(int i, int j)
{int fa_i find(i);int fa_j find(j);fa[fa_i] fa_j;
}相关练习题目
洛谷 P1551 亲戚
题目连接https://www.luogu.com.cn/problem/P1551
题目描述
若某个家族人员过于庞大要判断两个是否是亲戚确实还很不容易现在给出某个亲戚关系图求任意给出的两个人是否具有亲戚关系。
规定 x x x 和 y y y 是亲戚 y y y 和 z z z 是亲戚那么 x x x 和 z z z 也是亲戚。如果 x y xy xy 是亲戚那么 x x x 的亲戚都是 y y y 的亲戚 y y y 的亲戚也都是 x x x 的亲戚。
输入格式
第一行三个整数 n , m , p ( n , m , p ≤ 5000 ) n,m,p(n,m,p≤5000) n,m,p(n,m,p≤5000) 分别表示有 n n n 个人 m m m 个亲戚关系询问 p p p 对亲戚关系。
以下 m m m 行每行两个数 M i M j 1 ≤ M i M j ≤ n M_iM_j1≤M_iM_j≤n MiMj1≤MiMj≤n表示 M i M_i Mi 和 M j M_j Mj 具有亲戚关系。
接下来 p p p 行每行两个数 P i P j P_iP_j PiPj询问 P i P_i Pi 和 P j P_j Pj 是否具有亲戚关系。
输出格式 p p p 行每行一个Yes或No。表示第 i i i 个询问的答案为“具有”或“不具有”亲戚关系。
输入输出样例
# 输入
6 5 3
1 2
1 5
3 4
5 2
1 3
1 4
2 3
5 6# 输出
Yes
Yes
No题目解析
可以发现这是一个非常标准的并查集问题简直和并查集模版如出一辙因此直接将所有关系读取后进行合并然后直接查询父亲是否为同一个即可。
#includebits/stdc.h
using namespace std;#define ARR_LEN 6000int fa[ARR_LEN];void init(int n)
{for(int i 1; i n; i)fa[i] i;
}int find(int i)
{if(i fa[i]){return i;} else {fa[i] find(fa[i]);return fa[i];}
}void union(int i, int j)
{int fa_i find(i);int fa_j find(j);fa[fa_i] fa_j;
}int main()
{int n, m, p;int a, b;cin n m p;init(n);for(int i 0; i m; i){cin a b;union(a, b);}for(int i 0; i p; i){cin a b;int fa_a find(a);int fa_b find(b);if(fa_a fa_b)coutYesendl;elsecoutNoendl;}
}杭电 OJ1213 How Many Tables
题目连接https://acm.hdu.edu.cn/showproblem.php?pid1213
题目描述
Today is Ignatius’ birthday. He invites a lot of friends. Now it’s dinner time. Ignatius wants to know how many tables he needs at least. You have to notice that not all the friends know each other, and all the friends do not want to stay with strangers.
One important rule for this problem is that if I tell you A knows B, and B knows C, that means A, B, C know each other, so they can stay in one table.
For example: If I tell you A knows B, B knows C, and D knows E, so A, B, C can stay in one table, and D, E have to stay in the other one. So Ignatius needs 2 tables at least.
输入格式
The input starts with an integer T ( 1 T 25 ) T(1T25) T(1T25) which indicate the number of test cases. Then T T T test cases follow. Each test case starts with two integers N N N and M ( 1 N , M 1000 ) M(1N,M1000) M(1N,M1000). N N N indicates the number of friends, the friends are marked from 1 1 1 to N N N. Then M M M lines follow. Each line consists of two integers A A A and B ( A ! B ) B(A!B) B(A!B), that means friend A A A and friend B B B know each other. There will be a blank line between two cases.
输出格式
For each test case, just output how many tables Ignatius needs at least. Do NOT print any blanks.
输入输出样例
# 输入
2
5 3
1 2
2 3
4 55 1
2 5# 输出
2
4题目解析
分析可以发现这个问题要我们做的是统计在所有元素合并之后统计总共有多个和集合。很轻松就能写出下面的 AC 代码。类似的问题还有杭电 OJ1232 畅通工程。
读者大人可以在此基础上继续进行延伸我们实际生活中每个桌子只能坐 8 个人假设还需要考虑每桌人数的容量又如何进行改进呢
#includebits/stdc.h
using namespace std;#define ARR_LEN 6000int fa[ARR_LEN];void init(int n)
{for(int i 1; i n; i)fa[i] i;
}int find(int i)
{if(i fa[i]){return i;} else {fa[i] find(fa[i]);return fa[i];}
}void union(int i, int j)
{int fa_i find(i);int fa_j find(j);fa[fa_i] fa_j;
}int main()
{int n, m, a, b, t;cint;for(int i 0; i t; i){cinnm;int ans 0;init(n);for(int i 0; i m; i) {cinab;union(a, b);}for(int i 1; i n; i) {// 如果父亲是自己那么就表示一个独立的集合if(find(i) i)ans;}coutansendl;}}杭电 OJ1272 小希的迷宫
题目连接https://acm.hdu.edu.cn/showproblem.php?pid1272
题目描述
小希设计了一个迷宫让 Gardon 玩首先她认为所有的通道都应该是双向连通的就是说如果有一个通道连通了房间 A 和 B那么既可以通过它从房间 A 走到房间 B也可以通过它从房间 B 走到房间 A为了提高难度小希希望任意两个房间有且仅有一条路径可以相通除非走了回头路。小希现在把她的设计图给你让你帮忙判断她的设计图是否符合她的设计思路。比如下面的例子前两个是符合条件的但是最后一个却有两种方法从 5 到达 8。 输入格式
输入包含多组数据每组数据是一个以 0 0 结尾的整数对列表表示了一条通道连接的两个房间的编号。房间的编号至少为 1且不超过 100000。每两组数据之间有一个空行。整个文件以两个 -1 结尾。
输出格式
对于输入的每一组数据输出仅包括一行。如果该迷宫符合小希的思路那么输出Yes否则输出No。
输入输出样例
# 输入
6 8 5 3 5 2 6 4
5 6 0 08 1 7 3 6 2 8 9 7 5
7 4 7 8 7 6 0 03 8 6 8 6 4
5 3 5 6 5 2 0 0-1 -1# 输出
Yes
Yes
No题目解析
其实这个问题就是让我们判断一个连通图中是否存在环那么问题就转换为寻找出现环的条件。其实不难发现出现下面两种情况时连通图即存在环。
在查找过程中发现两个不同元素的父亲是相同的若不存在环则边的数量一定比顶点数量少 1。
#includebits/stdc.h
using namespace std;#define ARR_LEN 100010int fa[ARR_LEN];
bool visited[ARR_LEN]; // 用于辅助记录顶点的数量
int edges, points; // 记录顶点和边的数量
bool hascycle; // 是否存在环void init()
{hascycle false;edges 0;points 0;for(int i 1; i ARR_LEN; i)fa[i] i, visited[i] false;
}int find(int i)
{if(i fa[i]){return i;} else {fa[i] find(fa[i]);return fa[i];}
}void union(int i, int j)
{int fa_i find(i);int fa_j find(j);// 两个元素祖先相同存在环if(fa_i fa_j) {hascycle true;} else {visited[i] true;visited[j] true;edges;fa[fa_i] fa_j;}
}int main()
{int a, b;init();while(cinab) {if(a 0 b 0) {coutYesendl;continue;}if(a -1 b -1) {return 0;}union(a, b);while(cinab){if(a 0 b 0) {break;}union(a, b);}if(hascycle) {coutNoendl;continue;}for(int i 1; i ARR_LEN; i){if(visited[i]) {points;}}if(points edges 1) {coutYesendl;} else {coutNoendl;}init();}
}
