难度: Medium
Submission
运行时间: 26 ms
内存: 17.4 MB
class Solution:
def countComponents(self, n: int, edges: List[List[int]]) -> int:
def dfs(node, g, visited):
if node in g:
for n in g[node]:
if n not in visited:
visited.add(n)
dfs(n, g, visited)
return
g = {}
for edge in edges:
s, e = edge
if s not in g:
g[s] = []
g[s].append(e)
if e not in g:
g[e] = []
g[e].append(s)
ans = 0
visited = set()
for node in range(n):
if node not in visited:
visited.add(node)
ans += 1
dfs(node, g, visited)
return ans
Explain
这个题解使用深度优先搜索（DFS）来解决无向图中连通分量的数目问题。首先，通过遍历所有边构建图的邻接表表示。然后，对于每个节点，如果它还没有被访问过，就将连通分量的计数器加1，并从该节点开始进行DFS遍历，标记所有与之相连的节点为已访问。最终，连通分量的总数就是DFS遍历的次数。
时间复杂度: O(V+E)
空间复杂度: O(V+E)
class Solution:
def countComponents(self, n: int, edges: List[List[int]]) -> int:
def dfs(node, g, visited):
# 如果当前节点在图中有邻居节点
if node in g:
# 遍历当前节点的所有邻居节点
for n in g[node]:
# 如果邻居节点还没有被访问过
if n not in visited:
# 将邻居节点标记为已访问
visited.add(n)
# 递归访问邻居节点
dfs(n, g, visited)
return
# 构建图的邻接表表示
g = {}
for edge in edges:
s, e = edge
if s not in g:
g[s] = []
g[s].append(e)
if e not in g:
g[e] = []
g[e].append(s)
# 连通分量的计数器
ans = 0
# 记录已访问过的节点
visited = set()
# 遍历所有节点
for node in range(n):
# 如果当前节点还没有被访问过
if node not in visited:
# 将当前节点标记为已访问
visited.add(node)
# 连通分量的计数器加1
ans += 1
# 从当前节点开始进行DFS遍历
dfs(node, g, visited)
return ans
Explore
在构建邻接表时，对于每对边(s, e)，都需要将s添加到e的邻接列表中，同时将e添加到s的邻接列表中。这确保了无向图的双向关系得到反映。对于可能存在的孤立节点，即那些没有任何边与之相连的节点，它们在邻接表中可能不会显式出现。为确保这些节点也被考虑在内，可以在邻接表初始化时，为图中的每个节点预先创建一个空的邻接列表。这样，即使某些节点没有任何直接的边连接，它们也会在邻接表中有一个表示，从而在遍历所有节点时能正确统计到孤立节点。
在使用递归进行DFS遍历时，确实存在调用栈溢出的风险，特别是对于大规模的图和深图。为了避免这种情况，可以考虑使用迭代版本的DFS而不是递归。迭代版本的DFS使用显式的栈来模拟递归过程，从而避免了对系统调用栈的依赖。这样，即使是在非常大或深的图中，也不会出现栈溢出的问题。
在当前题解的DFS实现中，对于每个节点，首先检查它是否在邻接表`g`中。这是因为`g`可能不包含那些没有邻居的孤立节点。如果不进行这样的检查，对于孤立节点，程序将尝试访问`g[node]`时抛出错误，因为这样的键不存在于字典中。因此，这种检查是必要的，它确保了算法的健壮性，避免在尝试访问不存在的键时出错。
在实现中，使用一个集合`visited`来记录已经访问过的节点。在遍历所有节点时，只有当发现一个节点还未被访问，即`node not in visited`时，才会开始一个新的DFS遍历，并将连通分量的计数器增加1。这确保了每次开始新的DFS遍历都对应于一个新的连通分量，因为只有未被访问的节点才会触发新的DFS调用，从而标记出一个新的连通分量的所有节点。