最近看到一道这样的蓝桥杯题目：
问题描述
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题目一眼看上去并不困难，最直观的想法是用DFS暴力搜索一下，搜索过的地方标记一下即可找出共有多少连根植物。按照这个思路写了一下，结果只通过66%。然后看了一下解答，结果用的是并查集来解决这个问题。由于本身对这种数据结构使用的并不是很多而且不是很熟练，所以没有第一时间想到这个解法。在这里详细记录一下并查集的使用以及本题的解法。
并查集
并查集通过维护一个一维数组来实现，其本质是一个森林。刚开始每个节点都是孤立的，根就是自己。之后通过一些条件逐渐合并。用于处理一些不交集的合并及查询问题。 有一个联合-查找算法定义了两个用于此数据结构的操作： Find ：确定元素属于哪一个子集。 它可以被用来确定两个元素是否属于同一子集。
详细代码
下面直接看代码，在代码里一步步进行分析。
f = [0] * 1000 #定义并查集
def init(n):
for i in range(1, n+1):
f[i] = i #初始话并查集，每个节点的根是自己
def find_root(v):
if v == f[v]: # 如果当前节点的值就是自己的话，代表当前节点就是这棵树的根
return v # 直接返回即可
else:
f[v] = find_root(f[v]) # 如果不是，说明f[v]存的值只是中间节点，那么就去找f[v]的根，顺便 # 将当前节点的值改成根的值 这是一个递归的过程
return f[v] # 返回最后找到的根的值
def merge(u, v):
t1 = find_root(u) # u的根是t1
t2 = find_root(v) # v的根是t2
if t1 ！= t2: # 如果根相同，则这两个节点已经是同根了，不需要继续操作；如果不同，则需要合并
f[t2] = t1 # 不同的话，我们只需要将v的根t2的根（f[t2]的值）改成t1即可，表示t2的根是t1， # 这样t2下面所有节点就都属于t1了；这里其实用 f[t1] = t2也是一样的效果。
# 并查集的核心算法就是这些，其实很简单，下面就是针对具体题目了
if __name__ == '__main__': # 对于上述题目:
input_tmp = input()
m, n = int(input_tmp.split(' ')[0]), int(input_tmp.split(' ')[1])
size = m*n
init(size)
cmd_num = int(input())
for i in range(1, cmd_num+1):
input_tmp = input()
x, y = int(input_tmp.split(' ')[0]), int(input_tmp.split(' ')[1])
merge(x, y)
for i in range(1, n+1): # 最后找出有几个根，就是有几个不相交集，即答案
if f[i] == i:
s += 1
print(s)小结
算法倒是不难，只是一时没有想到。另外最近几天都没有更新啦，确实有一部分的原因在于我又摸鱼了，但是! 但是！最近事情也确实比较多，参与了一个5k star的大项目，又在整一下简历，另外其实我是正在写另一篇文章的。是关于linux部署的文章，但是在写文章复现的时候出现了一些莫名其妙的bug，折腾了两天都没有进展就卡住了，于是只好先弃坑，整理一下这个相对简单的问题，然后我打算完全重装一下服务器，重新实验一下，可能还需要几天，大概就是这样。
