解题思路:题目说合并各个点成为一个集合,是并查集的合并操作可以实现的
注意事项:python提交会超时,用c++AC了
参考代码:
class UnionFind: def __init__(self, grid): m, n = len(grid), len(grid[0]) # 行,列 self.count = 0 # 记录有几个集合 self.parent = [-1] * (m * n) self.rank = [0] * (m * n) # 记录集合的秩 for i in range(m): for j in range(n): if grid[i][j] == 1: self.parent[i * n + j] = i * n + j # 初始化每个元素的父亲结点都是自己 self.count += 1 # def find(self, i): # 找头结点 if self.parent[i] != i: # 如果自身的父结点不是自身,说明上层还有结点 self.parent[i] = self.find(self.parent[i]) # 递归调用,查找父结点的父结点,并进行了路径压缩 return self.parent[i] def union(self, x, y): # 合并集合,是由头结点代表一个集合,按秩合并 rootx = self.find(x) rooty = self.find(y) if rootx != rooty: # 两个结点不在同一个集合中才能合并 if self.rank[rootx] < self.rank[rooty]: # 将集合合并到秩大的集合里,此处只是为了让变量统一 rootx, rooty = rooty, rootx self.parent[rooty] = rootx if self.rank[rootx] == self.rank[rooty]: # 若被合并集合的秩一样大,那么就让合并集合的秩+1 self.rank[rootx] += 1 self.count -= 1 # 减少集合数,因为被合并了 def getCount(self): return self.count m, n = map(int, input().strip().split()) k = int(input().strip()) matrix = [[1 for _ in range(n)] for _ in range(m)] uf = UnionFind(matrix) for i in range(k): a, b = map(int, input().strip().split()) uf.union(a - 1, b - 1) print(uf.getCount())
0.0分
0 人评分
P1002 (C语言代码)浏览:970 |
C语言程序设计教程(第三版)课后习题10.4 (C语言代码)浏览:879 |
C语言程序设计教程(第三版)课后习题8.9 (C语言代码)浏览:817 |
三角形 (C语言代码)浏览:903 |
母牛的故事 (C语言代码)浏览:940 |
C语言程序设计教程(第三版)课后习题5.7 (C语言代码)浏览:756 |
拆分位数 (C语言代码)浏览:514 |
C语言程序设计教程(第三版)课后习题8.5 (C语言代码)浏览:656 |
拆分位数 (C语言代码)浏览:441 |
很简单,,题解1041:C语言程序设计教程(第三版)课后习题9.8 (C语言代码)浏览:586 |