Introduction

In directed graphs, a sink is usually a vertex with no outgoing edges. In the classic algorithm problem, people often mean a universal sink, which is even stricter: every other vertex must also point to it. This version is interesting because with an adjacency matrix you can find a candidate in linear time, and in the standard model you cannot generally do asymptotically better.

Define the Right Kind of Sink

For a graph with n vertices, a universal sink has two properties:

• out-degree 0
• in-degree n - 1

If the graph is stored as an adjacency matrix, that means:

• the sink's row contains only 0 values
• the sink's column contains 1 values for every other vertex

That matrix structure is what makes the efficient algorithm possible. If the graph is stored as adjacency lists instead, the cost model changes because checking incoming edges is no longer constant-time.

Eliminate Candidates One Comparison at a Time

The core observation is simple. Given two vertices u and v:

• if there is an edge from u to v, then u cannot be a universal sink
• otherwise v cannot be a universal sink

So one matrix lookup removes one candidate.

1def candidate_sink(matrix):
2    n = len(matrix)
3    candidate = 0
4
5    for vertex in range(1, n):
6        if matrix[candidate][vertex] == 1:
7            candidate = vertex
8
9    return candidate

After this pass, only one possible sink remains. That first loop takes n - 1 adjacency checks, so it runs in O(n) time.

Verification Is Required

The elimination pass only produces a candidate. It does not prove the candidate is actually a universal sink. You must verify both conditions against every other vertex.

1def find_universal_sink(matrix):
2    n = len(matrix)
3    candidate = candidate_sink(matrix)
4
5    for vertex in range(n):
6        if vertex == candidate:
7            continue
8
9        if matrix[candidate][vertex] != 0:
10            return None
11
12        if matrix[vertex][candidate] != 1:
13            return None
14
15    return candidate
16
17
18graph = [
19    [0, 1, 0, 1],
20    [0, 0, 0, 1],
21    [1, 1, 0, 1],
22    [0, 0, 0, 0],
23]
24
25print(find_universal_sink(graph))

The second pass also takes linear time, because it checks one row and one column of the candidate.

Why the Algorithm Works

The elimination logic never discards a real universal sink.

If candidate has an edge to vertex, then candidate cannot be a sink because sinks have no outgoing edges. Replacing it is safe.

If candidate does not have an edge to vertex, then vertex cannot be a universal sink, because a universal sink must have an incoming edge from every other vertex, including candidate.

So every comparison removes one impossible choice and preserves every remaining valid possibility.

Can You Beat O(V)?

With adjacency-matrix access, not in the worst case. Even after candidate elimination, a correct algorithm still has to verify the final vertex against the rest of the graph. That requires checking a linear number of entries.

There is also an information argument behind the lower bound. Before you inspect the relevant row and column positions, the remaining candidate might still hide:

• one outgoing edge, which would disqualify it
• or one missing incoming edge, which would also disqualify it

Any algorithm that claims correctness has to rule those possibilities out. That forces linear work in the worst case.

So the standard result is:

• adjacency matrix: O(V) time is achievable and asymptotically optimal
• adjacency list: the problem is not naturally better than inspecting relevant edge structure, which can cost O(V + E)

Representation Matters

Students often memorize the O(V) result and forget that it assumes constant-time access to A[u][v]. That is true for an adjacency matrix, but not for adjacency lists. In a list representation, asking whether there is an edge from u to v can itself take time proportional to the degree of u.

That is why algorithm complexity must always be tied to the input representation, not just the abstract graph problem.

Common Pitfalls

The most common mistake is skipping verification after candidate elimination. The first pass gives a possible sink, not a guaranteed one.

Another issue is solving the weaker “out-degree zero” problem instead of the universal sink problem. A universal sink must also receive edges from all other vertices.

Developers also ignore the representation assumption. The neat linear-time method depends on adjacency-matrix lookups being constant-time.

Finally, the diagonal entry usually does not matter. What matters is the candidate's relationship with every other vertex.

Summary

• A universal sink has out-degree 0 and in-degree n - 1.
• With an adjacency matrix, one pass can eliminate all but one candidate.
• A second pass must verify the candidate's row and column.
• The total running time is O(V).
• In the standard matrix-access model, that linear bound is already optimal.