Python Solution with Detailed Explanation

  • 1


    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]
        def adj(self, u):
            return self.nbr[u]
    class Solution(object):
        def dfs(self, v, visited, g):
            for nbr in g.adj(v):
                if nbr not in visited:
                    self.dfs(nbr, visited, g)
        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

Log in to reply

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