Dynamic connectivity contest |
---|
Finished |
Do you know anything about DFS, Depth First Search? For example, using this method, you can determine whether a graph is connected or not in O(E) time. You can even count the number of connected components in the same time.
Do you know anything about DSU, Disjoint Set Union? Using this data structure, you can process queries like "Add an edge to the graph" and "Count the number of connected components in the graph" fast.
And do you know how to solve Dynamic Connectivity Problem? In this problem, you have to process three types of queries fast:
At the first moment, the graph is empty.
The first line of file contains two integers N and K—number of vertices and number of queries (1 ≤ N ≤ 300 000, 0 ≤ K ≤ 300 000). Next K lines contain queries, one per line. There are three types of queries:
For each '?' query, output the number of connectivity components in the graph at the time of the query on a single line.
5 11
?
+ 1 2
+ 2 3
+ 3 4
+ 4 5
+ 5 1
?
- 2 3
?
- 4 5
?
5
1
1
2
Name |
---|