@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, rank): x_root = find_root(x, parent) y_root = find_root(y, parent) if x_root==y_root: return else: # 此处可以优化 # parent[x_root] = y_root 只写这一行可能会超时 if rank[x_root] > rank[y_root]: # x_root对应的树高较高 parent[y_root] = x_root # 将y_root对应的树挂到x_root对应的树 elif rank[x_root] < rank[y_root]: parent[x_root] = y_root else: parent[x_root] = y_root rank[y_root] += 1 # 此处+1是因为我们把x_root所在树挂在了y_root上，y_root树会高一层 return def main(): line = list(map(int, input().split())) row, col = line[0], line[1] rank = [0] + [-1 for i in range(row*col)] # 记录每个根节点所在的树高 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, rank) for i in parent: if i==-1: temp += 1 print(temp) return main()