Azret's blog

By Azret, history, 8 years ago, In English

Hello.

Given directed unweighted graph. It consist of N ≤ 105 vertices. There is at most one edge from each vertex. You need to answer for two types of queries (Q ≤ 105):

  1. Delete an edge from vertex V. Unexisting edge won't be deleted.
  2. Find shortest path from U to V.

No ideas. How to solve it?

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

»
8 years ago, # |
  Vote: I like it +2 Vote: I do not like it

*Each vertex has at most one outgoing edge

»
8 years ago, # |
Rev. 3   Vote: I like it +13 Vote: I do not like it

Nice problem! Here's how I would approach it.

Since each vertex has only at most one outgoing edge, each connected component has one of 3 possible structures:

  • A line, e.g. 0 -> 1 -> 2 -> 3

  • A simple cycle, e.g. 0 -> 1 -> 2 -> 3 -> 0

  • Line(s) ending in a cycle, e.g. 0 -> 1 -> 2 -> 3 -> 4 -> 2. The key is that there is only one cycle in any path because of the limit of outgoing edges.

The last one is annoying, but using the reverse graph makes things a bit simpler. Each node has only one incoming edge, which would make it tree except for the cycles. Suppose the given graph is D -> E -> A -> B -> C -> A, plus F-> A. The reverse graph is almost a tree:

A -> B -> C -> A

A -> E -> D

A -> F

To make it a tree, we shrink the cycle into a single vertex, saving the outgoing edge from the cycle to other vertices.

ABC -> E -> D

ABC -> F

Only the root of the tree can be a shrinked cycle. So, we have lists of lines from the root to the leaves. Only the root can have more than one outgoing edge, so the total length of the lists is O(N).

The shortest path from U to V is DistanceFromRoot(V) — DistanceFromRoot(U). If U is in the root and the root was a cycle, we need to check the distance from U to the end of the cycle.

To handle edge deletions, we can use an auxiliary data structure for each path to a leaf (every vertex belongs to a single line, except the root). Basically, we have a line A -> B -> U -> E -> F -> V -> Z, and we want to know if any node between U and V was deleted before. We can use their depth in the line and use a BST (e.g. C++ set) to save what vertices depths were deleted for each line.

It is a bit tricky to do this in the cycles, but they can be treated separately, in the same fashion.