← 返回 amazon 的题目列表Count connected components in an undirected graph (Union-Find)
类型：online_judge
Coding: Count connected components in an undirected graph (Union-Find)
Given an undirected graph with n nodes labeled 0 to n-1 and an edge list edges, compute the number of connected components.
Input
Line 1: integer n
Line 2: integer m (number of edges)
Next m lines: two integers u v describing an undirected edge between u and v
Output
A single integer: the number of connected components
Constraints
1 <= n <= 2 * 10^5
0 <= m <= 2 * 10^5
0 <= u, v < n
Multi-edges allowed; self-loops (u == v) do not change the number of components
Example 1
Input:
5
3
0 1
1 2
3 4
Output:
2
Example 2
Input:
4
0
Output:
4
Example
Input
5
3
0 1
1 2
3 4
Output
2