Python: DFS solution without recursion


  • 0
    C

    Approach:

    • Convert the edge list to adjacency list(dictionary with nodes as keys and neighbors as values)

    • Use a visited set to keep track of visited nodes

    • Make use of stack to perform the DFS whenever the stack runs out of nodes increment the count and push an unvisited node to the stack.

    from collections import defaultdict
    class Solution(object):
        def countComponents(self, n, edges):
            """
            :type n: int
            :type edges: List[List[int]]
            :rtype: int
            """
            
            adjList = defaultdict(list)
            
            for edge in edges:
                adjList[edge[0]].append(edge[1])
                adjList[edge[1]].append(edge[0])
            
            visited = set()
            stack = []
            count = 0
            
            for i in range(n):
                if i not in visited:
                    count += 1
                    stack.append(i)
                    
                    while len(stack)>0:
                        node = stack.pop()
                        visited.add(node)
                        
                        for nei in adjList[node]:
                            if nei not in visited:
                                stack.append(nei)
            
            return count

Log in to reply
 

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