Topological Sorting¶

In one sentence

If things must come before other things, repeatedly take one that nothing is still waiting on. If you get stuck before finishing, the requirements contain a cycle.

1. What problem does it solve?¶

Example — 510C · Fox and Names (rating 1600)

You are given \(n\) different names. Is there an order of the 26 letters (a new "alphabet") in which the names are sorted lexicographically? If so, print any such alphabet; otherwise print Impossible.

Lexicographic order: compare at the first position where the names differ; if one name is a prefix of the other, the shorter one comes first.

Limits: \(n \le 100\), each name has length \(\le 100\).

Input        Output
3
rivest
shamir
adleman      bcdefghijklmnopqrsatuvwxyz

7
car
care
careful
carefully
becarefuldontforgetsomething
otherwiseyouwillbehacked
goodluck     acbdefhijklmnogpqrstuvwxyz

Each pair of neighbouring names gives one rule. Compare them letter by letter. At the first difference, the letter in the earlier name must come before the letter in the later name. Nothing after that position matters.

For the second test:

earlier name	later name	first difference	rule
`car`	`care`	none, `car` is a prefix	OK, no rule
`care`	`careful`	none	OK
`careful`	`carefully`	none	OK
`carefully`	`becareful…`	position 0: `c` vs `b`	\(c \to b\)
`becareful…`	`otherwise…`	position 0: `b` vs `o`	\(b \to o\)
`otherwise…`	`goodluck`	position 0: `o` vs `g`	\(o \to g\)

Draw each rule as an arrow:

graph LR
  c --> b --> o --> g

We need an order of all 26 letters where every arrow points forward. The expected output acbdefhijklmnogpqrstuvwxyz has c before b, b before o, and o before g. Other orders are also accepted.

If a name is followed by its own prefix (like care then car), no alphabet helps, so print Impossible immediately. If the arrows form a cycle, such as \(a \to b \to a\), no order exists either.

2. The math¶

2.1 Words¶

DAG (directed acyclic graph): a directed graph with no cycle.
In-degree of \(v\): the number of arrows pointing into \(v\), meaning how many things must come before it that are not placed yet.

2.2 Fact: every DAG has a vertex with in-degree \(0\)¶

Suppose every vertex has in-degree \(\ge 1\). Start anywhere and keep walking backwards along an incoming arrow. Since every vertex has one, you never get stuck. After \(n + 1\) steps you have visited \(n + 1\) vertices, but there are only \(n\), so some vertex repeats. That repeat is a cycle, which contradicts "acyclic".

So a DAG always has a vertex that nothing depends on. It can safely go first.

2.3 Kahn's algorithm¶

Compute every in-degree. Put all in-degree-\(0\) vertices in a queue.
Pop \(u\) and append it to the order. "Remove" \(u\): for each arrow \(u \to v\), decrease the in-degree of \(v\). If it becomes \(0\), push \(v\).
When the queue is empty: if all \(n\) vertices were placed, that is the order. Otherwise there is a cycle.

Why it is correct. A vertex is placed only when all its predecessors were already placed, so every arrow points forward. Removing a vertex from a DAG leaves a DAG, so by §2.2 the queue is never empty while unplaced vertices remain. If there is a cycle, no vertex on it can ever reach in-degree \(0\), because each waits for the previous one. So they are never placed, and the count is less than \(n\).

2.4 Trace on the letters¶

Only \(b, o, g\) start with in-degree \(1\); every other letter starts at \(0\). Letters are numbered \(a = 0, \dots, z = 25\), so the queue starts in alphabetical order without \(b, o, g\):

step	pop	in-degree change	pushed	order so far
start			`a c d e f h … n p … z`
1	`a`	—		`a`
2	`c`	\(b: 1 \to 0\)	`b` (to the back)	`a c`
3–12	`d` … `n`	—		`a c d e f h i j k l m n`
13–24	`p` … `z`	—		`… n p q r s t u v w x y z`
25	`b`	\(o: 1 \to 0\)	`o`	`… z b`
26	`o`	\(g: 1 \to 0\)	`g`	`… z b o`
27	`g`	—		`… z b o g`

All 26 letters are placed, so the answer is acdefhijklmnpqrstuvwxyzbog. That differs from the sample output, but it satisfies every rule (\(c\) before \(b\) before \(o\) before \(g\)), and the problem accepts any valid alphabet.

2.5 Cost¶

Each vertex is pushed and popped once, and each arrow is looked at once. So \(O(V + E)\): here \(26\) letters and at most \(n - 1\) arrows. Building the rules costs \(O(n \cdot L)\) for names of length \(L\).

3. Templates¶

These are the templates we use in class. Use them exactly as written.

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:

Count how many edges point into each node (its in-degree).
Start with all nodes that have in-degree 0 — they depend on nothing.
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.
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.

4. Worked solution — Fox and Names¶

Build one arrow per neighbouring pair, then run the lesson's topo_sort on 26 vertices (letter a is vertex \(0\)).

import sys
from collections import deque

input = sys.stdin.readline


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


def solve():
    n = int(input())
    names = [input().strip() for _ in range(n)]

    edges = []
    for i in range(n - 1):
        s = names[i]
        t = names[i + 1]
        j = 0
        while j < len(s) and j < len(t) and s[j] == t[j]:
            j += 1
        if j == len(s) or j == len(t):
            if len(s) > len(t):         # a longer name before its own prefix
                print("Impossible")
                return
        else:
            edges.append((ord(s[j]) - ord('a'), ord(t[j]) - ord('a')))

    order = topo_sort(26, edges)
    if order is None:
        print("Impossible")
        return

    for x in order:
        print(chr(x + ord('a')), end="")
    print()


solve()

Repeated rules (the same arrow twice) are harmless: the in-degree counts both copies, and both are removed when the letter is popped.

5. DP on a DAG¶

A topological order is also the right order for dynamic programming on a graph. When you reach \(v\), every \(u\) with an arrow \(u \to v\) is already finished.

AtCoder EDU DP G · Longest Path (you solved this on July 5)

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

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

Process vertices in topological order, and relax each outgoing arrow len[nxt] = max(len[nxt], len[node] + 1). The answer is max(len).

6. Common mistakes¶

Arrow in the wrong direction

"\(x\) must come before \(y\)" is the arrow \(x \to y\), and it increases the in-degree of \(y\). Reversing it prints the order backwards.

Missing the prefix case

abc followed by ab is impossible even though no letters differ. Without that check, you output a valid-looking alphabet for an impossible input.

Comparing past the first difference

Only the first differing position gives a rule. Letters after it say nothing about the order.

Not checking for a cycle

If fewer than \(n\) vertices were placed, the answer is Impossible. The template returns None in that case, so 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(), as the template does.

7. Practice¶

Problem	Where	Idea
510C · Fox and Names	Codeforces · 1600	this page
AtCoder EDU DP G · Longest Path	AtCoder (July 5)	DP in topological order
919D · Substring	Codeforces · 1700	topo order + DP over 26 letters, cycle ⇒ −1
1385E · Directing Edges	Codeforces · 2000	orient undirected edges along a topological order

Credits & licenses

Description of Kahn's algorithm (§2.3 steps): adapted and translated from OI Wiki — Topological Sort by marscheng1 and other OI Wiki contributors, licensed CC BY-SA 4.0.
Section structure and the problems 510C and 1385E follow USACO Guide — Topological Sort by Benjamin Qi and Nathan Chen, licensed CC BY-NC-SA 4.0.
Everything else (the in-degree-0 proof, the correctness argument, the letter trace, worked solution) is ours. The template in §3 is from our lessons.