Topological Sorting

In one sentence

Repeatedly take a vertex that nothing points into any more. On a DAG this gives an order where every arrow points forward. On a graph with cycles it peels off the chains and leaves the cycles behind.

Where we are

• 12 Jul: Kahn's algorithm (§1).
• 5 Jul: EDU DP G, DP in topological order (§2).
• 18 Oct (Set 13): Kahn on a functional graph, peeling the chains off the cycles: H, H2 and I (§3).
• 25 Oct: H and H2 written in class; only the popped vertices count towards the answer (§3.3, §3.4).

1. Kahn's algorithm (lesson of 12 Jul)

The notes from class:

What it is

Topological sorting orders the nodes of a directed acyclic graph (DAG) so that for every edge u → v, u comes before v. Think of it as figuring out a valid order to do tasks when some tasks depend on others (e.g. "put on socks before shoes").

It only works on graphs with no cycles — if there's a cycle, no valid order exists.

Kahn's Algorithm (BFS + Queue)

The idea:

1. Count how many edges point into each node (its in-degree).
2. Start with all nodes that have in-degree 0 — they depend on nothing.
3. Repeatedly remove a zero-in-degree node, add it to the result, and decrease the in-degree of its neighbors. Any neighbor that drops to 0 joins the queue.
4. If you processed every node, you have a valid order. If not, there's a cycle.

Python code

from collections import deque

def topo_sort(n, edges):
    adj = [[] for _ in range(n)]
    deg = [0] * n

    for u, v in edges:          # edge u -> v means u before v
        adj[u].append(v)
        deg[v] += 1

    queue = deque(i for i in range(n) if deg[i] == 0)
    order = []

    while queue:
        node = queue.popleft()
        order.append(node)
        for nxt in adj[node]:
            deg[nxt] -= 1
            if deg[nxt] == 0:
                queue.append(nxt)

    return order if len(order) == n else None   # None = cycle


# Example: 0 -> 1 -> 3, 0 -> 2 -> 3
print(topo_sort(4, [(0, 1), (0, 2), (1, 3), (2, 3)]))   # [0, 1, 2, 3]

Key points

• Time complexity: O(V + E) — you visit every node and edge once.
• Multiple valid answers: the output depends on queue order; many orderings can be correct.
• Cycle detection is free: if fewer than num_nodes nodes end up in the result, the graph has a cycle.

2. DP on a DAG — EDU DP G · Longest Path (5 Jul)

In a DAG, find the number of edges on the longest directed path.

When a vertex is popped, every vertex pointing into it was popped earlier, so its value is final. Push it forward along each outgoing edge:

\[ \mathrm{dp}_v = \max_{u \to v} \big(\mathrm{dp}_u + 1\big), \qquad \mathrm{dp}_v = 0 \text{ if nothing points to } v . \]

The code from class:

def solve():
    n, m = map(int, input().split())

    # in-deg for each vertex
    deg = [0 for _ in range(n)]
    adj = [[] for _ in range(n)]
    for i in range(m):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        adj[u].append(v)
        deg[v] += 1

    q = deque()
    for i in range(n):
        if deg[i] == 0:
            q.append(i)

    dp = [0 for _ in range(n)]

    while q:
        u = q.popleft()
        for v in adj[u]:
            dp[v] = max(dp[v], dp[u] + 1)
            deg[v] -= 1
            if deg[v] == 0:
                q.append(v)

    print(max(dp))

3. Lessons of 18 and 25 Oct — peeling chains off a directed graph

3.1 The idea

Run Kahn's algorithm on a graph with cycles. It does not crash: it removes every vertex it can, then the queue runs empty.

• A vertex on a cycle is never removed: the vertex before it on the cycle is waiting for its own predecessor, all the way round.
• So the algorithm eats the graph from the ends of the chains inwards, and stops at the cycles.

In a functional graph (every vertex has exactly one outgoing edge) this means: removed = the tails, left = exactly the cycle vertices. That is a second way to find the cycles, next to walking along a[i] with three states (Set 13 · G).

Only in a functional graph

In a general directed graph, vertices after a cycle are left too. In \(1 \to 2 \to 1\), \(2 \to 3\), vertex \(3\) is not on a cycle, but it never reaches in-degree \(0\) because \(2\) is never removed.

3.2 The template from class

When we only want to peel, the order of the pops does not matter, so a plain list used as a stack is fine.

    adj = [[] for _ in range(n + 1)]
    in_degree = [0 for _ in range(n + 1)]

    for _ in range(m):
        u, v = map(int, input().split())
        adj[u].append(v)
        in_degree[v] += 1

    end = []
    for i in range(1, n + 1):
        if in_degree[i] == 0:
            end.append(i)

    while len(end) > 0:
        cur = end.pop()
        # removed[cur]=True

        for nxt in adj[cur]:
            in_degree[nxt] -= 1
            if in_degree[nxt] == 0:
                end.append(nxt)

end holds the current ends of chains. In a functional graph adj[cur] is the single vertex a[cur], so the for loop is just nxt = a[cur].

The useful part: when cur is popped, everything that flows into cur is already finished, exactly like the DP in §2. So we can push a value forward to a[cur] while peeling. H, H2 and I below are three choices of that value.

3.3 H · 2044G1 · Medium Demon Problem (easy) (rating 1700)

Each spider \(i\) starts with one plushie. Every year, each spider that has a plushie gives one to \(r_i\); anyone left with more than one throws the extras away. Find the first year in which the process is stable.

• A spider on a cycle always has \(1\): it gives one and gets one from the cycle.
• A spider nobody gives to (in-degree \(0\)) has \(0\) after year \(1\), forever.
• Then a spider that only receives from spiders already at \(0\) reaches \(0\) one year later, and so on towards the cycle.

So depth[v] = the year after which \(v\) is \(0\): leaves start at \(1\), and when popping v, depth[r[v]] = max(depth[r[v]], depth[v] + 1). Why can v report straight to r[v] at the moment it is popped? Because the topological order guarantees that every child of v was popped before v, so depth[v] is already final. (This is the same thing as a memoized DFS, done bottom-up.)

The answer is the largest depth among the popped vertices, plus \(2\) (just \(2\) if there are no tails). Cycle vertices also receive values, but they never empty, so they must not be counted.

Sample: r = [2, 1, 4, 2, 3], i.e. \(5 \to 3 \to 4 \to 2\) and the cycle \(1 \rightleftarrows 2\).

pop	depth	change
5	1	in-degree of \(3\): \(1 \to 0\), push
3	2	in-degree of \(4\): \(1 \to 0\), push
4	3	in-degree of \(2\): \(2 \to 1\), stop

\(\max = 3\), answer \(5\).

3.4 H2 · 2044G2 · Medium Demon Problem (hard)

Same, but extra plushies are kept. Every plushie that ever flows into \(v\) has to leave \(v\) one per year, so \(v\) is empty after size[v] years, where size[v] counts \(v\) and everyone that eventually flows into it.

What changes from H (lesson of 25 Oct): start with size = 1 everywhere, and when popping v, size[r[v]] += size[v] (add, not max). Keep a result outside the loop and update it when a vertex is popped: result = max(result, size[v]). The answer is result + 2.

The test from class: n = 4, r = 2 1 1 1. Vertices \(3\) and \(4\) both point into the cycle \(1 \rightleftarrows 2\). The popped vertices are \(3\) and \(4\), each with size \(1\), so the answer is \(3\). Taking the max over all vertices would also see size[1] = 3 and print \(5\).

3.5 I · 1872F · Selling a Menagerie (rating 1800)

Animal \(i\) is afraid of \(a_i\). Sell all animals in some order; selling \(i\) gives \(2 c_i\) if \(a_i\) is not sold yet, otherwise \(c_i\). Print an order with the largest total.

• \(i\) is doubled exactly when \(i\) is sold before \(a_i\).
• Tails: sell them in peeling order. Each is sold before the one it points to, so all are doubled.
• Cycles: going all the way round would need \(x\) before \(x\), so one animal per cycle must lose. Let it be the cheapest: start at a[cheapest], walk round, and the cheapest is sold last.

def solve():
    n = int(input())
    a = [0] + list(map(int, input().split()))
    c = [0] + list(map(int, input().split()))

    indeg = [0] * (n + 1)
    for i in range(1, n + 1):
        indeg[a[i]] += 1

    order = []
    sold = [False] * (n + 1)
    q = deque()
    for i in range(1, n + 1):
        if indeg[i] == 0:
            q.append(i)
    while q:
        v = q.popleft()
        sold[v] = True
        order.append(v)
        u = a[v]
        indeg[u] -= 1
        if indeg[u] == 0:
            q.append(u)

    for i in range(1, n + 1):
        if sold[i]:
            continue

        # i is on a cycle that we have not handled yet
        cheapest = i
        v = a[i]
        while v != i:
            if c[v] < c[cheapest]:
                cheapest = v
            v = a[v]

        v = a[cheapest]
        while not sold[v]:
            sold[v] = True
            order.append(v)
            v = a[v]

    print(*order)

Many orders are optimal, so your output may differ from the sample. Only the total matters.

4. Common mistakes

Not checking for a cycle

On a DAG problem, if fewer than \(n\) vertices were placed there is a cycle. Do not print a partial order.

Using list.pop(0) as the queue

pop(0) is \(O(n)\) per call. Use collections.deque and popleft().

Treating every leftover vertex as a cycle vertex

True only in a functional graph (§3.1).

Taking the max over every vertex in H and H2

Cycle vertices get pushed into too, but they are never popped. Update the answer only when a vertex is popped (test: 4 / 2 1 1 1, answer 3).

Using = instead of max for depth in H

Two tails can meet at one vertex. The longest one decides, not the one popped last.

5. Practice

Problem	Where	Idea
EDU DP G · Longest Path	AtCoder (5 Jul)	DP in topological order
2044G1 · Medium Demon Problem (easy)	Set 13 · H	peel the tails, push depth forward with max
2044G2 · Medium Demon Problem (hard)	Set 13 · H2	same, push size forward
1872F · Selling a Menagerie	Set 13 · I	peel the tails, then break each cycle at its cheapest