Interesting task on direct graph
Difference between en4 and en5, changed 3 character(s)
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 <= 1000000, M <= 10000000, queries <= 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?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en6 English 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 English Domonion 2019-09-16 23:56:18 3 Tiny change: 's <= 1000$ ,\nShould b' -> 's <= 1000$.\nShould b'
en4 English Domonion 2019-09-16 23:55:50 7 Tiny change: 'We have set of graph $G$' -> 'We have graph $G$'
en3 English Domonion 2019-09-16 23:55:34 85
en2 English Domonion 2019-09-16 23:51:15 8 Tiny change: ' 1000000, M <= 1000$,' -> ' 1000000, queries <= 1000$,'
en1 English Domonion 2019-09-16 23:45:10 334 Initial revision (published)