Знаете ли Вы что-нибудь про DFS, Depth First Search, поиск в глубину?
Например, используя этот метод, можно проверить связность графа за время O(E). Можно даже за тоже самое время посчитать число компонент связности графа.
Знаете ли Вы что-нибудь про DSU, Disjoint Set Union, систему непересекающихся множеств? Используя эту структуру данных, Вы можете обрабатывать запросы вида "Добавить ребро в граф" и "Посчитать число компонент связности графа" быстро. Т.е. оба запроса за O(log N).
А знаете ли Вы что-нибудь про Dynamic Connectivity Problem? В этой задаче, вам нужно уметь быстро обрабатывать 3 типа запросов:
Добавить ребро в граф.
Удалить ребро из графа.
Посчитать число компонент связности графа.
Изначально граф пуст.
Первая строка входного файла содержит 2 числа — N и K — число вершин и число запросов (1 ≤ N ≤ 300000, 0 ≤ K ≤ 300000).
Следующие K содержат запросы, по одному в строке. Есть 3 типа запросов:
+ u v: добавить ребро между вершинами u и v. Гарантируется, что в момент получения запроса такого ребра в графе нет.
- u v: удалить ребро между вершинами u и v. Гарантируется, что в момент получения запроса такое ребро в графе есть.
?: посчитать число компонент связности в графе в текущий момент.
Вершины нумеруются от 1 до N. Нет запросов с u = v. Граф неориентированный.
Для каждого запроса вида '?' выведите число компонент связности графа в момент времени запроса на отдельной строке.