0323. 无向图中连通分量的数目

0323. 无向图中连通分量的数目 #

  • 标签:深度优先搜索、广度优先搜索、并查集、图
  • 难度:中等

题目大意 #

给定 n 个节点(编号从 0n - 1)的图的无向边列表 edges,其中 edges[i] = [u, v] 表示节点 u 和节点 v 之间有一条无向边。

要求:计算该无向图中连通分量的数量。

解题思路 #

利用深度优先搜索和 visited 数组标记。

  • 从未遍历过的节点 u 出发,连通分量数量加 1。然后遍历与 u 节点构成无向边,且为遍历过的的节点 v
  • 再从 v 出发继续深度遍历。
  • 直到遍历完与u 直接相关、间接相关的节点之后,再遍历另一个未遍历过的节点,继续上述操作。
  • 最后输出连通分量数目。

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def dfs(self, visited, i, graph):
        visited[i] = True
        for j in graph[i]:
            if not visited[j]:
                self.dfs(visited, j, graph)

    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        count = 0
        visited = [False for _ in range(n)]
        graph = [[] for _ in range(n)]

        for x, y in edges:
            graph[x].append(y)
            graph[y].append(x)

        for i in range(n):
            if not visited[i]:
                count += 1
                self.dfs(visited, i, graph)
        return count
本站总访问量  次  |  您是本站第  位访问者