Problem
Đồ thị vô hướng có n đỉnh nhưng không có cạnh. m cạnh dần dần được thêm vào biểu đồ.
Sau mỗi lần thêm một cạnh, bạn cần tìm số lượng các thành phần được kết nối.
Một biểu đồ có thể có các vòng và nhiều cạnh.
Đầu vào:
Dòng đầu tiên chứa hai số - n và m (1 <= n <= 300000, 0 <= m <= 500000) - số đỉnh của đồ thị và số cạnh được thêm vào.
m dòng tiếp theo chứa hai số u, v (1 <= u, v <= n) - chúng có nghĩa là một cạnh (u, v) đã được thêm vào biểu đồ.
Đầu ra:
Sau mỗi lần thêm một cạnh, hãy in số lượng thành phần liên thông của biểu đồ.
|
Nhập |
Đầu ra |
|
3 2
1 2
2 3
|
2
1 |
|
36
1 1
2 2
3 3
1 1
2 2
1 2
|
3
3
3
3
3
2
|
(c) Ibrahim Ahmad, 2018