*Each vertex has at most one outgoing edge

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.