# Python Solution with Detailed Explanation

• Solutions

Number of Connected Components in an Undirected Graph https://leetcode.com/problems/number-of-connected-components-in-an-undirected-graph/

Depth First Search: O(V+E)

• Build a graph using the list of edges. Maintain a set called visited to track the nodes which have been visited so far.
• Iterate through all vertices and call DFS on each unvisited vertex. The DFS on that vertex will mark all reachable nodes with that vertex. That constitutes a component abd we increment the count for components.
``````class G(object):
def __init__(self, n, edges):
self.nbr = {}
for i in range(n):
self.nbr[i] = []
for edge in edges:
u, v = edge[0], edge[1]
self.nbr[u].append(v)
self.nbr[v].append(u)
return

return self.nbr[u]

class Solution(object):
def dfs(self, v, visited, g):
if nbr not in visited:
self.dfs(nbr, visited, g)
return

def countComponents(self, n, edges):
"""
:type n: int
:type edges: List[List[int]]
:rtype: int
"""
g = G(n, edges)
visited = set([])
components = 0
for v in range(n):
if v not in visited:
self.dfs(v, visited, g)
components += 1
return components
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.