学习笔记7"/>
python学习笔记7
题目链接
- 题目中给了邻接链表,转为邻接矩阵
- 初始化邻接矩阵 graph = [[] for _ in range(n)]
- dfs() 的写法, 用visi避免重复访问,得到每个点所在的联通分量中点的个数
class Solution:def countPairs(self, n: int, edges: List[List[int]]) -> int:graph = [[] for _ in range(n)]for x, y in edges:graph[x].append(y)graph[y].append(x)visi = [False] * ndef dfs(x: int) -> int:visi[x] = Truecount = 1for y in graph[x]:if not visi[y]:count += dfs(y)return countres = 0for i in range(n):if not visi[i]:count = dfs(i)res += count * (n - count)return res // 2
更多推荐
python学习笔记7
发布评论