[LeetCode] 323. Number of Connected Components in an Undirected Graph

 Problem : https://leetcode.com/problems/number-of-connected-components-in-an-undirected-graph/

Use DFS to find all connected nodes.

A stack based DFS solution:

class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        
        graph = defaultdict(list)
        
        for a, b in edges:
            graph[a].append(b)
            graph[b].append(a)
                    
        result = 0
        seen = set()
        stack = []
        
        for i in range(n):
            if i not in seen:
                result += 1
                
                seen.add(i)
                stack.append(i)
                
                while stack:
                    a = stack.pop()
                    
                    for b in graph[a]:
                        if b not in seen:
                            seen.add(b)
                            stack.append(b)
        
        return result