Problem statement

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

Solution

All we need to do is to run dfs (or bfs) from all possible starts if node is not visited yet and calculate number of components.

Complexity

It is just $O(E+n)$ for time and $O(n)$ for space. If we have used union find with ranks and path compression it would be the same.

Code

class Solution:
    def countComponents(self, n, edges):
        graph = defaultdict(list)
        visited = [0]*n
        for x, y in edges:
            graph[x].append(y)
            graph[y].append(x)
            
        def dfs(node, color):
            visited[node] = color
            for neib in graph[node]:
                if visited[neib] == 0:
                    dfs(neib, color)
        
        col = 1
        for i in range(n):
            if visited[i] == 0:
                dfs(i, col)
                col += 1
            
        return max(visited)