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] * n
        def dfs(x: int) -> int:
            visi[x] = True
            count = 1
            for y in graph[x]:
                if not visi[y]:
                    count += dfs(y)
            return count

        res = 0
        for i in range(n):
            if not visi[i]:
                count = dfs(i)
                res += count * (n - count)

        return res // 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23