323 Number of Connected Components in an Undirected Graph

Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to find the number of connected components in an undirected graph.

Example 1:
     0          3
     |          |
     1 --- 2    4
Given n = 5 and edges = [[0, 1], [1, 2], [3, 4]], return 2.

Example 2:
     0           4
     |           |
     1 --- 2 --- 3
Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [3, 4]], return 1.

Note:

• You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.

The Idea: First build the undirected graph. Then iterate through each possible element in the graph, and perform a DFS if the element has not been visited. Every successive DFS will explore the graph within it's setting and therefore counts as a connected component.

Complexity: O(N) time and O(2n) space

class Solution:
    def countComponents(self, n, edges):
        """
        :type n: int
        :type edges: List[List[int]]
        :rtype: int
        """

        visited = [False for _ in range(0, n)]
        graph = {i: [] for i in range(0, n)}
        for edge in edges:
            graph[edge[0]].append(edge[1])
        for edge in edges:
            graph[edge[1]].append(edge[0])

        def DFS(start):
            if not visited[start]:
                visited[start] = True
                for i in graph[start]:
                    DFS(i)

        count = 0
        for i in range(0, n):
            if not visited[i]:
                DFS(i)
                count += 1

        return count