Python Solution with Detailed Explanation


  • 1
    G

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

Log in to reply
 

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