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.
Input
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.
Output
For each conn query output YES or NO. Pay attention to letter case.
Example
Input:
4 11
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
Output:
YES
YES
NO
YES
This example will be the first test case.
hide comments
punitive1729:
2021-05-12 11:02:01
Is there some resource to study about it. It would be incredibly helpful if someone can share some links. Thanks in advance
|
|
lovro_nidogon1:
2020-11-03 14:38:25
ez |
|
petkov:
2019-03-01 17:54:05
The constrains are not too tight. I solved it with segment tree + partially persistent dsu. You don't need link/cut trees. |
|
tanavya:
2017-12-08 20:25:29
TLE :( constraints too tight. |
|
dacin21:
2016-01-10 20:52:26
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. |
|
immortalco:
2015-10-04 10:54:46
The problem description is wrong.
|
|
immortalco:
2015-10-04 10:52:58
A tough task.
|
|
jkelava6:
2015-01-04 14:09:10
"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 |
Added by: | indy256 |
Date: | 2011-09-22 |
Time limit: | 2s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |