Count Connected Components in an Undirected Graph

Given n labeled nodes from 0 to n - 1 and an undirected edge list, return the number of connected components in the graph. This is the classic DSU find-root task: use representatives to decide whether two nodes are already in the same set.

Input Format

n = number of nodes, edges = undirected edges

Output Format

number of connected components

Constraints

  • 1 <= input size <= 10^5
  • -10^9 <= numeric values <= 10^9
  • Input must satisfy the format described in inputFormat.

Examples

Example 1:

Input:

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

Output:

2

Explanation:

Nodes {0,1,2} are one component and {3,4} are the second.

Example 2:

Input:

n = 2
edges = [[0,1]]

Output:

1

Example 3:

Input:

n = 4
edges = [[0,1],[1,2],[2,3]]

Output:

1

Explanation:

All nodes are linked in one chain.

Loading...
Count Connected Components in an Undirected…