一、合根植物
试题链接：[蓝桥杯 2017 国 C] 合根植物
问题描述
星球的一个种植园，被分成 m×n 个小格子(东西方向 m 行，南北方向 n 列)。每个格子里种了一株合根植物。这种植物有个特点，它的根可能会沿着南北或东西方向伸展，从而与另一个格子的植物合成为一体。如果我们告诉你哪些小格子间出现了连根现象，你能说出这个园中一共有多少株合根植物吗?
输入描述
第一行，两个整数 m，n，用空格分开，表示格子的行数、列数(1 < m,n < 1000)。
接下来一行，一个整数 k，表示下面还有k 行数据(0 < k< 10^5)。
接下来k行，每行两个整数 a，b，表示编号为 a的小格子和编号为b的小格子合根了。
格子的编号一行一行，从上到下，从左到右编号。比如:5x4的小格子，编号:
| 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 1919 20
9 13
13 17
输出样例
5
样例解释
问题分析
首先由题目可知最多可能有10^6个数据，所以我们设置列表的时候要设置够数量。
对于任给的两个节点，要将其接在一起，就用merge函数来实现，即把第一个节点（树）挂在第二个节点（树）上。
find函数是用来找该节点的“祖宗”（根节点）的，fa列表表示第i个节点的父节点，我们在调用find函数时也不断地更新父节点，让其变为其根节点。
find函数和merge函数都要记下的。
最后我们来判断一下根节点有几个（根节点一直没动，其值i就等于fa[i]）
代码示例
def merge(x,y):
fa[find(x)]=find(y)
def find(x):
if x==fa[x]:
return x
else:
fa[x]=find(fa[x])
return fa[x]
if __name__=="__main__":
fa=[i for i in range(1000000)]
m,n=map(int,input().split())
k=int(input())
for i in range(k):
a,b=map(int,input().split())
merge(a,b)
x=m*n
ans=0
for i in range(1,x+1):
if i ==fa[i]:
ans+=1
print(ans)
二、修改数组
试题链接：[蓝桥杯 2019 省 A] 修改数组
问题描述
输入示例
5
2 1 1 3 4
输出示例
2 1 3 4 5
问题分析
对于该题，我们可以用树来做，好处是：比如在输入样例中，1已经出现了一次，那么我们自动会更新其fa[1]=3（即其根节点为3）那么我们在再次遇到1时即可直接得出3，而不用判断1是否在之前出现过，2（1+1）是否在之前出现过。
代码实现过程我们用了find函数和merge函数这两个最基本的（必须记下来）函数。
find函数可以实现，对每一个数都可以求出他的祖宗（根节点）；而merge函数可以让树两两结合在一起，比如我们2出现了一次，那么我们就让2和（2+1）连接在一起，即把2挂在2+1上面，且fa[2]=fa[2+1]（此时2+1的根节点就为自身）。这时又出现了1，同样的，我们把1挂在1+1=2上面，那么fa[1]=fa[1+1]=fa[2]=fa[2+1]，这时若再出现1，那么输出fa[1]=fa[3]=3.在树的结构上，往前走一格刚好就是+1（从已经存在的点开始，沿着树枝的方向连续走，一直走到根节点的前一个，这些数都存在，所以都不能停，直到变成根节点，才符合题目要求）。
代码示例
def find(x):
if x==fa[x]:
return x
else:
fa[x]=find(fa[x])
return fa[x]
def merge(x,y):
fa[find(x)]=find(y)
if __name__=="__main__":
n=int(input())
ls=input().split()
fa=[i for i in range(1000010)]
for i in ls:
a=int(i)
b=find(a)
print(b,end=" ")
merge(b,b+1)