2024年最新【Python 百练成钢】快速上手并查集(2)，Python面试简历模板

💗问题描述💗

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

接下来一行,一个整数k,示下面还有k行数据(0

接下来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)]

测试数据

做了那么多年开发，自学了很多门编程语言，我很明白学习资源对于学一门新语言的重要性，这些年也收藏了不少的Python干货，对我来说这些东西确实已经用不到了，但对于准备自学Python的人来说，或许它就是一个宝藏，可以给你省去很多的时间和精力。

别在网上瞎学了，我最近也做了一些资源的更新，只要你是我的粉丝，这期福利你都可拿走。

我先来介绍一下这些东西怎么用，文末抱走。

（1）Python所有方向的学习路线（新版）

这是我花了几天的时间去把Python所有方向的技术点做的整理，形成各个领域的知识点汇总，它的用处就在于，你可以按照上面的知识点去找对应的学习资源，保证自己学得较为全面。

最近我才对这些路线做了一下新的更新，知识体系更全面了。

（2）Python学习视频

包含了Python入门、爬虫、数据分析和web开发的学习视频，总共100多个，虽然没有那么全面，但是对于入门来说是没问题的，学完这些之后，你可以按照我上面的学习路线去网上找其他的知识资源进行进阶。

（3）100多个练手项目

我们在看视频学习的时候，不能光动眼动脑不动手，比较科学的学习方法是在理解之后运用它们，这时候练手项目就很适合了，只是里面的项目比较多，水平也是参差不齐，大家可以挑自己能做的项目去练练。

（4）200多本电子书

这些年我也收藏了很多电子书，大概200多本，有时候带实体书不方便的话，我就会去打开电子书看看，书籍可不一定比视频教程差，尤其是权威的技术书籍。

基本上主流的和经典的都有，这里我就不放图了，版权问题，个人看看是没有问题的。

（5）Python知识点汇总

知识点汇总有点像学习路线，但与学习路线不同的点就在于，知识点汇总更为细致，里面包含了对具体知识点的简单说明，而我们的学习路线则更为抽象和简单，只是为了方便大家只是某个领域你应该学习哪些技术栈。

（6）其他资料

还有其他的一些东西，比如说我自己出的Python入门图文类教程，没有电脑的时候用手机也可以学习知识，学会了理论之后再去敲代码实践验证，还有Python中文版的库资料、MySQL和HTML标签大全等等，这些都是可以送给粉丝们的东西。