Domonion's blog

Interesting task on direct graph
By Domonion, history, 5 years ago, In English

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?

  • Vote: I like it
  • +9
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Auto comment: topic has been updated by Domonion (previous revision, new revision, compare).

→ Reply
»
5 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Auto comment: topic has been updated by Domonion (previous revision, new revision, compare).

→ Reply
»
5 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Auto comment: topic has been updated by Domonion (previous revision, new revision, compare).

→ Reply
»
5 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Auto comment: topic has been updated by Domonion (previous revision, new revision, compare).

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Dynamic connectivity

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How to apply dynamic connectivity to directed graph?

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 :(

→ Reply