Number of connected components in an undirected graph

First we will create an adjacency list of the graph from the edges. Then we will use a depth-first search to solve this problem. We will keep track of the number of connected components. We will iterate over the nodes of the graph. If a node is not visited, we will increment the number of connected components and perform a depth-first search on the node.

class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        graph = collections.defaultdict(list)
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)
        visited = set()
        res = 0
        for node in range(n):
            if node not in visited:
                res += 1
                self.dfs(node, graph, visited)
        return res

    def dfs(self, node, graph, visited):
        visited.add(node)
        for nei in graph[node]:
            if nei not in visited:
                self.dfs(nei, graph, visited)

Time complexity: O(n)
Space complexity: O(n)