给定一个 n 个节点的邻接矩阵 m。 节点定义为城市,如果 a 城市与 b 城市相连, b 与 c 城市相连,尽管 a 与 c 并不直接相连,但可以认为 a 与 c 相连,定义 a,b,c 是一个城市群。
矩阵 m[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连,否则表示不相连。
请你找出共有多少个城市群。
数据范围: , 矩阵中只包含和
[[1,1,0],[1,1,0],[0,0,1]]
2
1 2 相连,3 独立,因此是 3 个城市群。
[[1,1,0,0],[1,1,1,0],[0,1,1,0],[0,0,0,1]]
2
1 , 2相连 ;2 ,3相连,4独立,因此是 1,2,3 属于一个城市群,4属于一个城市群。
# python3 # 并查集做法 # 总城市肯定是m # 每有两个城市互相连接,数量就减1 class Solution: def __init__(self): self.n = 210 self.father = [i for i in range(self.n)] def find(self, u): if u == self.father[u]: return u self.father[u] = self.find(self.father[u]) return self.father[u] def same(self, u, v): u = self.find(u) v = self.find(v) if u == v: return True return False def join(self, u, v): u = self.find(u) v = self.find(v) if u == v: return self.father[u] = v pass def citys(self , m: List[List[int]]) -> int: # write code here cnt = len(m) for i in range(len(m)): for j in range(len(m[0])): if m[i][j] == 1: if not self.same(i, j): self.join(i, j) cnt -= 1 else: continue return cnt