【蓝桥杯】合根植物
原创
题目：
w 星球的一个种植园，被分成 m×n 个小格子（东西方向 m 行，南北方向 n 列）。每个格子里种了一株合根植物。 这种植物有个特点，它的根可能会沿着南北或东西方向伸展，从而与另一个格子的植物合成为一体。 如果我们告诉你哪些小格子间出现了连根现象，你能说出这个园中一共有多少株合根植物吗？
题解函数;
def find_root(parents, i):
if parents[i] == i:
return i
parents[i] = find_root(parents, parents[i])
return parents[i]
def union(parents, ranks, i, j):
root_i = find_root(parents, i)
root_j = find_root(parents, j)
if root_i != root_j:
if ranks[root_i] > ranks[root_j]:
parents[root_j] = root_i
elif ranks[root_i] < ranks[root_j]:
parents[root_i] = root_j
else:
parents[root_j] = root_i
ranks[root_i] += 1
def count_roots(m, n, connections):
total_cells = m * n
parents = [i for i in range(total_cells)]
ranks = [0] * total_cells
for connection in connections:
i1, j1, i2, j2 = connection
index1 = i1 * n + j1
index2 = i2 * n + j2
union(parents, ranks, index1, index2)
root_set = set()
for i in range(total_cells):
root_set.add(find_root(parents, i))
return len(root_set)find_root(parents, i): 这个函数用于找到并返回元素 i 所在集合的根。它实现了路径压缩，将 i 到根的路径上的所有节点都直接连接到根，以优化后续查找操作。
union(parents, ranks, i, j): 这个函数用于将两个集合进行合并。首先，它找到 i 和 j 的根节点 root_i 和 root_j，然后根据两个根节点的秩（rank）来确定哪个根节点将成为合并后的根。如果 root_i 的秩较大，将 root_j 的父节点更新为 root_i，反之亦然。如果两个根节点的秩相等，选择其中一个作为新的根，并将其秩增加 1。
count_roots(m, n, connections): 这个函数接受三个参数，分别是种植园的行数 m、列数 n 和一个包含连根现象的列表 connections。在函数内部，首先初始化并查集的父节点列表 parents 和秩列表 ranks，然后遍历 connections 列表，通过调用 union 函数将连接的树进行合并。最后，通过遍历整个种植园，使用 find_root 函数找到每个元素所在集合的根，并将这些根节点添加到集合 root_set 中。最终，函数返回 root_set 的长度，即合根植物的数量。
示例用法：在这个示例中，种植园的行数为 3，列数为 3，存在三个连接，分别是 (0,0) 到 (0,1)，(0,1) 到 (1,1)，(2,0) 到 (2,1)。调用 count_roots 函数计算并打印出合根植物的数量。
调试代码
m = 3
n = 3
connections = [[0, 0, 0, 1], [0, 1, 1, 1], [2, 0, 2, 1]]
result = count_roots(m, n, connections)
print(result)原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。