👾前言👾
众所周知并查集是一种非常牛X的数据结构,有了他某些问题可以大大的简化
本篇博客重在分享几个利用并查集解决的问题。如果需要学习并查集的话还请你去c一下
因为在c站上已经有了许多优秀的关于并查集基础概念的分享。
🍁前置知识🍁
并查集是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。
常常在使用中以森林来表示。集就是让每个元素构成一个单元素的集合，也就是按一定顺序
将属于同一组的元素所在的集合合并。
并查集描述了集合之间的关系,并查集有主要需要三个函数
init()： 将所有的点进行初始化find()：找根节点union()：合并两个集合
为了节约空间咱们还可以进行路径压缩,具体如何实现呢,快块看题吧。
假设你已经会了并查集,咱们直接上题😸
🤺练习题🤺
🌺畅通工程🌺
💗问题描述💗
Problem Description
某省调查城镇交通状况，得到现有城镇道路统计表，
表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通
（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。问最少还需要建设多少条道路？
Input
测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数，分别是城镇数目N ( < 1000 )和道路数目M；
随后的M行对应M条道路，每行给出一对正整数，分别是该条道路直接连通的两个城镇的编号。为简单起见，城镇从1到N编号。
注意:两个城市之间可以有多条道路相通,也就是说
3 3
1 2
1 2
2 1
这种输入也是合法的
当N为0时，输入结束，该用例不被处理。
Output
对每个测试用例，在1行里输出最少还需要建设的道路数目。
Sample Input
4 2
1 3
4 3
3 3
1 2
1 3
2 3
5 2
1 2
3 5
999 0
0
Sample Output
1
0
2
998
Huge input, scanf is recommended.
💗问题分析💗
典型的使用并查集进行解决的问题,先将并查集建立起来,然后判断有几个根节点
有n个根节点就需要再修建n-1条路将其连接起来。
💗代码实现💗
def init(n): return {k:k for k in range(1,n+1)} def find(mem,n): while mem[n]!=n: n=mem[n] return n def union(mem,a,b): t1=find(mem,a) t2=find(mem,b) if t1!=t2: mem[t1]=t2 ans=[] while True: ls=list(map(int,input().split())) if ls[0]==0: break mem=init(ls[0]) side=[list(map(int,input().split())) for i in range(ls[1])] for i in side: if find(mem,i[0])!=find(mem,i[1]): union(mem,i[0],i[1]) ans.append(len([i for i in mem if mem[i]==i])-1) # 这里减去1是因为len之后是树的个数,而需要添加的边应比树的数目少1即可。 for i in ans: print(i)
🌺合根植物🌺
💗问题描述💗
w星球的一个种植园,被分成m * n个小格子(东西方向m行，北方向n列)。每个格子里种了-株合根植物。
这种植物有个特点，它的根可能会沿着南北或东西方向伸展，从而与另一个格子的植物合成为-体。
如果我们告诉你哪些小格子间出现了连根现象，你能说出这个园中-共有多少株合根植物吗?
输入格式：
第一行，两个整数m, n,用空格分开，示格子的行数、列数(1 <m,n<1000)。
接下来一行,一个整数k,示下面还有k行数据(0<k< 100000)
接下来k行，第行两个整数a, b,表示编号为a的小格子和编号为b的小格子合根了。
格子的编号一行一 行,从上到下,从左到右编号。
比如: 5* 4的小格子,编号:
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
17 18 19 20
样例输入：
5 4
16
2 3
1 5
5 9
4 8
7 8
9 10
10 11
11 12
10 14
12 16
14 18
17 18
15 19
19 20
9 13
13 17
样例输出
5
💗问题分析💗
题目问的是有几个合根植物,那么就是问的在这篇森林中有几颗子树
我们可以将边集中的所有点进行合并,最后判断根节点的个数得出答案
💗代码实现💗
def init(n): return {k:k for k in range(1,n+1)} def find(mem,a): # 到了根节点 while mem[a]!=a: # 路径压缩 mem[a]=mem[mem[a]] a=mem[a] return a def union(mem,a,b): mem[find(mem,a)]=mem[find(mem,b)] m,n=map(int,input().split()) k=int(input()) mem=init(m*n) ls=[list(map(int,input().split())) for i in range(k)] for i in ls: union(mem,i[0],i[1]) print(len([i for i in mem if mem[i]==i]))
🌺远方的亲戚🌺
💗问题描述💗
例子:现在有若干家族图谱关系，给出了一些亲戚关系，如Marry和Tom是亲戚， Tom和Ben是亲戚等等。 从这些信息中，你可以推
导出Marry和Ben是亲戚。请写-一个程序，对于我们的关于亲戚关系的提问，以最快速度给出答案。
[输入格式]
第一部分是以N,M开始。N为人数(1<=N<=20000)，这 些人的编号为1 ,2,…N。.下面有M行(1<=M<= 000000)，每行有两个数a,b,表
示a和b是亲戚。
第二部分是以Q开始。以下Q行有Q个询问(1<=Q<=1000000),每行为c,d,表示询问c和d是否为亲戚。
[输出格式]
对于询问c,d,输出一行:若c,d为亲戚，则输出"YES"，否则输出"NO"
[输入样例]
10 7
2 4
5 7
1 3
8 9
1 2
5 6
2 3
3
3 4
7 10
8 9
[输出样例]
YES
NO
YES
💗问题分析💗
这个题目更加简单,就是判断一下两个节点的根节点是否相同
如果相同的话有亲属关系,否则没有亲属关系。
💗代码实现💗
def init(m): return {k:k for k in range(1,m+1) } def find(mem,n): while mem[n]!=n: n=mem[n] return n def union(memls,a,b): t1=find(mem,a) t2=find(mem,b) if t1!=t2: memls[t1]=t2 # 键入人数与关系数 m,n=map(int,input().split()) # 初始化关系树 mem=init(m) # 键入n组关系 ls1=[list(map(int,input().split())) for i in range(n)] # 测试数据 k=int(input()) ls2=[list(map(int,input().split())) for i in range(k)] ans=[] for i in ls1: union(mem,i[0],i[1]) for i in ls2: if find(mem,i[0])==find(mem,i[1]): ans.append("YES") else: ans.append("NO") for i in ans: print(i)
🌺并查集解决最小生成树问题🌺
💗问题描述💗
给定一个n个点m条边的无向图，图中可能存在重边和自环，边权可能为负数。
求最小生成树的树边权重之和，如果最小生成树不存在则输出impossible.
给定一张边带权的无向图G=(V, E),其中V表示图中点的集合, E表示图中边的集合，n=|V|, m=|E|。
由V中的全部n个顶点和E中n-1条边构成的无向连通子图被称为G的一棵生成树，其中边的权值之和最小的生成树被
称为无向图G的最小生成树。
输入格式
第一行包含两个整数n和m。
接下来m行，每行包含三个整数u, v, w,表示点u和点v之间存在一条权值为w的边。
输出格式
共一行，若存在最小生成树，则输出一个整数,表示最小生成树的树边权重之和，如果最小生成树不存在则输出
impossible。
数据范围
1<n≤105,
1<m<2*10,
图中涉及边的边权的绝对值均不超过1000。
输入样例:
4 5
1 2 1
1 3 2
1 4 3
2 3 2
3 4 4
输出样例:
6
💗问题分析💗
使用克鲁斯卡尔的思想,进行求解。
先对边集进行排序，然后判断两点是不是属于同一颗树,不是的话进行合并
并将路权加载最后的ans内。直到加到n-1条边，t跳出循环
如果某点最终无法加进来必定最后的根节点有大于或等于2个
此时无法建立最小生成树
💗代码实现💗
def init(n): return {k:k for k in range(1,n+1)} def find(mem,a): while mem[a]!=a: mem[a]=mem[mem[a]] a=mem[a] return a def union(mem,a,b): mem[find(mem,a)]=mem[find(mem,b)] n,m=map(int,input().split()) ls=[list(map(int,input().split())) for i in range(m)] # 去除自环 ls=[i for i in ls if i[0]!=i[1]] ls.sort(key=lambda x:x[2]) ans=0 ansside=[] mem=init(n) for i in ls: if find(mem,i[0])!=find(mem,i[1]): union(mem,i[0],i[1]) ans+=i[2] ansside.append([i[0],i[1]]) if len([i for i in mem if mem[i]==i])>=2: print("impossible") else: print(ans) print(ansside)
