Interesting task on direct graph

Правка en6, от Domonion, 2019-09-17 00:03:07

We have graph $G$ and 4 types of queries:

1. Add/Remove set of direct edges $(uv)$.
2. Mark vertex $v$.
3. 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?

#### История

Правки

Rev. Язык Кто Когда Δ Комментарий
en6 Domonion 2019-09-17 00:03:07 22 Tiny change: 'v$.\n\n$N <= 100000, M <= 1000000, ' -> 'v$.\n\n$N \leq 100000, M \leq 1000000, '
en5 Domonion 2019-09-16 23:56:18 3 Tiny change: 's <= 1000$,\nShould b' -> 's <= 1000$.\nShould b'
en4 Domonion 2019-09-16 23:55:50 7 Tiny change: 'We have set of graph $G$' -> 'We have graph $G$'
en3 Domonion 2019-09-16 23:55:34 85
en2 Domonion 2019-09-16 23:51:15 8 Tiny change: ' 1000000, M <= 1000$,' -> ' 1000000, queries <= 1000$,'
en1 Domonion 2019-09-16 23:45:10 334 Initial revision (published)