Interesting task on direct graph

Revision en5, by Domonion, 2019-09-16 23:56:18

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?

Tags graphs, directed graph, task

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)