Problem description:

You have a graph of n nodes. You are given an integer n and an array edges where edges[i] = [ai, bi] indicates that there is an edge between ai and bi in the graph.

Return the number of connected components in the graph.

Example 1:

https://assets.leetcode.com/uploads/2021/03/14/conn1-graph.jpg

1
2
Input: n = 5, edges = [[0,1],[1,2],[3,4]]
Output: 2

Example 2:

https://assets.leetcode.com/uploads/2021/03/14/conn2-graph.jpg

1
2
Input: n = 5, edges = [[0,1],[1,2],[2,3],[3,4]]
Output: 1

Constraints:

  • 1 <= n <= 2000
  • 1 <= edges.length <= 5000
  • edges[i].length == 2
  • 0 <= ai <= bi < n
  • ai != bi
  • There are no repeated edges.

Solution:

DFS:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        graph = defaultdict(list)
        for edge in edges:
            graph[edge[0]].append(edge[1])
            graph[edge[1]].append(edge[0])
        
        visited = [False for _ in range(n)]
        
        def dfs(node):
            if visited[node]:
                return
            visited[node] = True
            for neighbor in graph[node]:
                dfs(neighbor)
        
        res = 0
        for i in range(n):
            if not visited[i]:
                res += 1
                dfs(i)
        return res

Union find

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:    
        def find(n, parent):
            if n == parent[n]:
                return n
            else:
                parent[n] = find(parent[n], parent)
                return parent[n]
        # union find, start with n nodes
        parent = [i for i in range(n)]
        res = n
        for edge in edges:
            p1 = find(edge[0], parent)
            p2 = find(edge[1], parent)
            if p1 != p2:
                parent[p2] = parent[p1]
                res -= 1 
        return res

time complexity: $O()$
space complexity: $O()$
reference:
related problem: