Components over Time

Difficulty: 1850 4000 ms 128 MB

union-find

Edges arrive one by one on N initially-isolated nodes. After EACH edge, print the number of connected components.

Input: the first line has N and M; each of the next M lines has an edge u v.

Output: M lines: the component count after each edge.

Constraints:

• 1 ≤ N, M ≤ 10⁵

Sample Tests

4 3
1 2
3 4
2 3

3
2
1

2 2
1 1
1 2

2
1

Read the Editorial