Free Graphs lessonsGraphs · Stage 1 · Depth-first · Step 3

Remember what each place leads to

When many routes pass through the same place, count its routes once and reuse the answer. About 15 minutes.

One-way streets with no loops

Think of a river that splits and joins, or the prerequisites in a course plan. Every connection goes one way, and you can never return to a place you left. A graph like that is called a directed acyclic graph, or DAG for short.

How many different routes lead from the first place to the last? You could follow every route to the end and count them, but routes share long stretches, and the number of routes can be astronomical.

DAG: one-way connections and no way back to where you were.

Ask your neighbours, then remember

Here is the trick. The number of routes from a place to the end does not depend on how you arrived. So ask each neighbour how many routes it has, and add the answers up. The end itself has exactly one: stopping there.

Write each answer down the first time you work it out. When another route reaches the same place, read the answer off instead of exploring again. Every place is worked out once, which makes the count fast even when the number of routes is huge.

Routes from a place: the sum of routes from each neighbour.

Write it down: each place is solved once and then reused.

In code

adj = [[] for _ in range(n)]
for u, v in edges:
    adj[u].append(v)
memo = {}
def ways(node):
    if node == n - 1:
        return 1
    if node in memo:
        return memo[node]
    total = 0
    for nxt in adj[node]:
        total += ways(nxt)
    memo[node] = total
    return total
return ways(0)

Routes from 0 to 4, where every street goes one way

Count the routes from 0 to 4. Ask each neighbour how many routes it has, then add the answers.

Move 1 of 6

Quick check

A place has two streets leading on. One neighbour has 3 routes to the end and the other has 4. How many routes does the place have?

Show the answer

7. Every route goes through exactly one of the two neighbours, so add: 3 + 4.

Your problem

How many routes?

There are n places, numbered 0 to n − 1, joined by one-way streets. edges[i] = [a, b] means you can drive from place a to place b, and a < b for every street, so there are never any loops. Return how many different routes lead from place 0 to place n − 1. A route may pass through any places.

Example

n = 5, edges = [[0, 1], [0, 2], [1, 2], [1, 3], [2, 3], [3, 4]] → 3

1 ≤ n ≤ 50 · the answer fits in a long

Solve it in your browserFree account, no card. Python, C++, Java or JavaScript, with hints if you get stuck, and your progress is saved.