解题思路:题目说合并各个点成为一个集合,是并查集的合并操作可以实现的
注意事项: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 人评分
C语言考试练习题_排列 (C语言代码)浏览:725 |
C语言训练-自由落体问题 (C语言代码)浏览:615 |
A+B for Input-Output Practice (V) (C语言代码)浏览:468 |
C语言程序设计教程(第三版)课后习题6.7 (C语言代码)浏览:684 |
简单的a+b (C语言代码)浏览:830 |
C语言训练-8除不尽的数 (C语言代码)浏览:1402 |
1162答案错误,为什么浏览:644 |
整数分类 oj上总是wrong answer浏览:664 |
P1044 (C++代码)浏览:494 |
C语言程序设计教程(第三版)课后习题7.4 (C++代码)浏览:557 |