DYNACON2 - Dynamic Graph Connectivity
A graph initially consists of N (1 ≤ N ≤ 100,000) unconnected vertices. The vertices are numbered from 1 to N.
Your task is to maintain that graph and answer connectivity queries.
All edges in the problem are undirected.
You will receive the following queries, where (1 ≤ A, B ≤ N) :
- add A B : add an edge between vertices A and B, where initially there is no path between A and B.
- rem A B : remove edge between vertices A and B, where initially there is an edge between A and B.
- conn A B : print YES if there is a path between A and B and NO otherwise, where A and B are different.
The first line of input contains the number of vertices N and the number of queries M (1 ≤ M ≤ 100,000). The following M lines contain queries.
For each conn query output YES or NO. Pay attention to letter case.
add 1 2
add 2 3
add 3 4
add 1 4
conn 4 2
rem 1 2
conn 2 4
rem 3 4
conn 4 2
add 2 4
conn 4 2
This example will be the first test case.
Is there some resource to study about it. It would be incredibly helpful if someone can share some links. Thanks in advance
The constrains are not too tight. I solved it with segment tree + partially persistent dsu. You don't need link/cut trees.
TLE :( constraints too tight.
For those who want a challenge, one can actually solve this problem using an on-line algorithm (answer each querry before you read the next one)! Because that's what i did.
The problem description is wrong.
A tough task.
"where initially there is no path between A and B" - but first 4 commands of the example form a square. "add 1 4" breaks that rule! Please fix!Last edit: 2015-01-04 14:22:13