@Python实现
# 利用并查集 # 并查集的关键就是 find_root函数 和 union函数()； # find_root函数：(寻找节点的根节点) # union函数：判断如果某条边的两个顶点的root节点一样，说明这两个点在同一个树上(或者说在同一个集合内)，此时也说明另一个问题：该“树”一定存在环【有环的就不叫树喽！！】 # 如果root节点不一样，说明这两个顶点处于两个集合中，那么既然他俩有边，可以对这两个集合进行union：parent[x_root] = y_root 或 parent[y_root] = x_root都可以！！ def find_root(x, parent): if parent[x] == -1: return x while parent[x]!=-1: x = parent[x] return x def union(x, y, parent): x_root = find_root(x, parent) y_root = find_root(y, parent) if x_root==y_root: return parent[x_root] = y_root return def main(): line = list(map(int, input().split())) row, col = line[0], line[1] parent = [0] + [-1 for i in range(row*col)] # 将所有顶点的父节点初始化为-1，即每个顶点先单独成为一个集合 edges = int(input()) temp = 0 for i in range(edges): line = list(map(int, input().split())) x, y = line[0], line[1] union(x, y, parent) for i in parent: if i==-1: temp += 1 print(temp) return main()