Detecting the sink in a directed acyclic graph

Question

Let's say that there is one vertex with the following property in a DAG:

1. All vertices are connected to it

2. It is not connected to any vertex

This is usually called a sink vertex.

Is it possible to detect this vertex in O(n), where n is number of vertices in graph?

Answer 1

As there are no cycles in the graph, and all vertex connect with the sink, just select any starting node and start walking randomly. When you can't continue walking, you are at the sink, in at most n steps.

Once you walked n steps (or less and you can't continue), as the problem does not guarantee that there is a sink, you should check if you are at one. That adds another O(n). So the problem is O(2 n) = O(n)

Answer 2

The best I can think of is O(n + m) which is O(n) if m is O(n).

Assuming a sink exists, do a topological sort of the graph. The minimal node in the sort is a sink. Note that topological sort is O(n + m).

I have previously provided an implementation here which can easily be modified for this problem.

Answer 3

Provided you can count the number of edges in/out of a node in linear time, it's possible. First, find the vertices that have no outgoing edges (O(n) to scan all nodes). Your conditions are satisfied only if there's exactly one such vertex. Then, count its incoming edges (O(n) to scan all input edges). Your conditions are satisfied if there are exactly n-1 incoming edges. If either test fails, there's no sink vertex.

I'm assuming by "connected" you mean "connected by an edge", not "reachable by a path".