Модуль: Система непересекающихся множеств


Задача

5 /9


Ребра

Задача

Есть n вершин неориентированного графа, в нем же нет ребер. В граф постепенно добавляются m ребер. 
После каждого добавления ребра требуется узнать количество компонент связности.
В графе могут быть петли и кратные ребра.

Входные данные:
В первой строке два числа  - n и m (1 <= n <= 300000, 0  <= m <= 500000) - количество вершин графа и количество добавляемых ребер. 
В следующих m строках по два числа u, v (1 <= u, v <= n) - они значат, что в граф добавили ребро (u, v).
Выходные данные:
После каждого добавления ребра выведите количество компонент связности графа.

Ввод Вывод
3 2
1 2
2 3
2
1
3 6
1 1
2 2
3 3
1 1
2 2
1 2
3
3
3
3
3
2

(с) Ибрахим Ахмад, 2018



time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w648
Комментарий учителя