Number of Sinks in a DAG

Number of Sinks in a DAG is a gentle graph warm-up that drills one idea: a vertex's role is decided entirely by its out-degree — the number of edges leaving it. A sink is simply a vertex that nothing leaves.

The slow way first

You might reach for a traversal — DFS or BFS from every vertex, checking which ones lead nowhere. That works but is overkill: it visits edges repeatedly and costs far more than the problem needs.

The question to ask: what actually makes a vertex a sink? Nothing about reachability or depth — only whether any arrow leaves it. That is a purely local property, and we can read it straight off the edge list.

The idea: tally out-degrees, count the zeros

Make an out-degree counter for every vertex. Sweep the edge list once: every edge u → v adds one to outdeg[u]. Then sweep the vertices once: each vertex whose outdeg is 0 is a sink, so bump the count.

The key insight: a sink is defined by out-degree, not in-degree. An isolated vertex (no edges at all) is still a sink, because nothing leaves it either.

Walk through it

Step through the animation. First the DAG appears with an out= label under each vertex. Then we walk A through E. A, B, and C each have arrows leaving, so they are skipped. D has out-degree 0 and turns green — a sink. E has no edges at all, so it is a sink too. The final count is 2.

Pseudocode

outdeg = array of zeros, one slot per vertex
for each edge (u, v):
    outdeg[u] += 1            # u has an outgoing edge
count = 0
for each vertex v:
    if outdeg[v] == 0:        # nothing leaves v
        count += 1            # v is a sink
return count

The Python solution

def count_sinks(n, edges):
    outdeg = [0] * n
    for u, v in edges:
        outdeg[u] += 1
    count = 0
    for v in range(n):
        if outdeg[v] == 0:
            count += 1
    return count

• outdeg has one slot per vertex, all starting at zero.
• The first loop reads each edge (u, v) and increments outdeg[u] — only the source of an arrow gains out-degree.
• count accumulates the answer.
• The second loop checks every vertex; line 7 is the heart of it — outdeg[v] == 0 means no arrow leaves v.
• Isolated vertices never get touched in the first loop, so they keep out-degree 0 and are correctly counted as sinks.

Complexity

We trade O(V) extra space (the out-degree array) for a single linear sweep. No traversal, no recursion — just two counting passes.

When this pattern shows up

Practice