Number of Connected Components in an Undirected Graph

Problem: Number of Connected Components in an Undirected Graph

We can run depth-first search to get number of connected components.

Code in Python:

from collections import defaultdict

class Solution(object):
    def countComponents(self, n, edges):
        """
        :type n: int
        :type edges: List[List[int]]
        :rtype: int
        """
        res = 0
        adj, visited = defaultdict(list), [False] * n

        for u,v in edges:
            adj[u].append(v)
            adj[v].append(u)

        for i in xrange(n):
            if not visited[i]:
                res += 1
                visited[i] = True
                stack = [i]
                while stack:
                    u = stack.pop()
                    for v in adj[u]:
                        if not visited[v]:
                            visited[v] = True
                            stack.append(v)

        return res