We have graph $$$G$$$ and 4 types of queries:
- Add/Remove set of direct edges $$$(uv)$$$.
- Mark vertex $$$v$$$.
- Check for some vertex $$$v$$$ if there is a path from marked vertex $$$u$$$ to $$$v$$$.
$$$N \leq 100000, M \leq 1000000, queries \leq 1000$$$. Should be better $$$O(N^2)$$$, online.
There are no more than $$$1000$$$ edges in $$$1$$$ query
I have no idea how to solve this, any hint?
Auto comment: topic has been updated by Domonion (previous revision, new revision, compare).
Auto comment: topic has been updated by Domonion (previous revision, new revision, compare).
Auto comment: topic has been updated by Domonion (previous revision, new revision, compare).
Auto comment: topic has been updated by Domonion (previous revision, new revision, compare).
Dynamic connectivity
How to apply dynamic connectivity to directed graph?
If this can be solved another version of the problem can also be solved in which you also have queries of unmarking a vertex. Add a fake vertex(call it 0) to G and only 0 is marked at the beginning. each query of mark/unmark a vertex v will be add/remove edge (0v). But I don't think the initial problem can be solved :(