Lexicographic Ordering

Priority queue topological sort picks lexicographically smallest available node

The Smallest Answer Isn't Always Obvious

Alien dictionary: derive character ordering DAG from sorted words

Standard Kahn's gives some valid topological order. But what if the problem demands the lexicographically smallest one? You can't just sort the output -- that would violate dependency constraints.

The fix is exactly one line of change: swap the queue for a min-heap. But understanding why this works (and why the DFS approach fails here) separates people who memorize from people who understand.

Why a Queue Isn't Enough

In standard Kahn's, when multiple nodes have in-degree 0 simultaneously, the queue processes them in FIFO order -- whichever happened to reach in-degree 0 first. That's arbitrary. It doesn't guarantee lexicographic order.

Consider nodes {3, 1, 5} all at in-degree 0. A queue might pop them in order 3, 1, 5. But lex-smallest needs 1 first.

Solution: Replace the queue with a min-priority-queue (min-heap). At every step, pop the smallest available node.

priority_queue<int, vector<int>, greater<int>> pq;
for (int i = 1; i <= n; i++)
    if (indeg[i] == 0) pq.push(i);

vector<int> order;
while (!pq.empty()) {
    int u = pq.top(); pq.pop();
    order.push_back(u);
    for (int v : adj[u])
        if (--indeg[v] == 0) pq.push(v);
}

That's it. Identical to Kahn's, with priority_queue instead of queue.

Greedy Correctness

Why does always picking the smallest available node produce the lex-smallest ordering?

Think about it position by position. For position 0, we want the smallest node that can legally go first. That's the smallest node with in-degree 0. After placing it, for position 1, we want the smallest node with in-degree 0 in the remaining graph. And so on.

At each step, the min-heap gives us exactly that node. No future choice can improve on picking the smallest available node now.

💡 Key insight. Lex-smallest topological order is a greedy algorithm. At every position, pick the smallest node whose prerequisites are all satisfied. The min-heap makes this efficient.

Trace on an Example

DAG: 1:[3], 2:[3], 4:[5], 3:[5], 5:[]

Nodes: {1, 2, 3, 4, 5}

Initial in-degrees: 1:0, 2:0, 3:2, 4:0, 5:2

Step	Heap	Pop	Decrement	Order
0	{1, 2, 4}	--	--	[]
1	{2, 4}	1	3→1	[1]
2	{4}	2	3→0, push 3	[1, 2]
3	{4}	3	5→1	[1, 2, 3]
4	{}	4	5→0, push 5	[1, 2, 3, 4]
5	{}	5	--	[1, 2, 3, 4, 5]

Result: 1 2 3 4 5.

What would standard Kahn's (FIFO queue, seeded as {1, 2, 4}) give? Possibly 1 2 4 3 5 -- which is valid but not lex-smallest.

Why DFS Doesn't Work Here

You might think: run DFS in sorted neighbor order, take the reversed post-order. This does NOT produce the lex-smallest topological order.

Consider: 2 → 1, 3 → 1. DFS from node 2 first gives post-order [1, 2], then DFS from 3 gives [3]. Reversed: [3, 2, 1]. But the lex-smallest order is [2, 3, 1].

The problem is that DFS commits to exploring one branch fully before considering alternatives. It can't make the globally greedy choice at each position.

⚠ Gotcha. DFS-based topological sort with sorted neighbors does NOT produce lex-smallest order. Only the priority-queue Kahn's approach works. This is a common trap in contests.

AtCoder abc223_d -- Restricted Permutation

Problem: Given N items and M constraints "item A must come before item B," find the lexicographically smallest valid permutation. If impossible, print -1.

This maps directly to lex-smallest topological order:

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> adj[n + 1];
    vector<int> indeg(n + 1, 0);

    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        indeg[b]++;
    }

    priority_queue<int, vector<int>, greater<int>> pq;
    for (int i = 1; i <= n; i++)
        if (indeg[i] == 0) pq.push(i);

    vector<int> order;
    while (!pq.empty()) {
        int u = pq.top(); pq.pop();
        order.push_back(u);
        for (int v : adj[u])
            if (--indeg[v] == 0) pq.push(v);
    }

    if ((int)order.size() < n) {
        cout << -1 << endl;
    } else {
        for (int i = 0; i < n; i++)
            cout << order[i] << (i + 1 < n ? " " : "\n");
    }
}

Checking Uniqueness (abc291_e)

Sometimes the question is: "Is the topological order unique?"

Rule: The topological order is unique if and only if the queue/heap never contains more than one element at any point during Kahn's algorithm.

If the queue ever has 2+ elements, we had a choice. A choice means multiple valid orderings.

bool unique = true;
priority_queue<int, vector<int>, greater<int>> pq;
for (int i = 1; i <= n; i++)
    if (indeg[i] == 0) pq.push(i);

vector<int> order;
while (!pq.empty()) {
    if (pq.size() > 1) unique = false;
    int u = pq.top(); pq.pop();
    order.push_back(u);
    for (int v : adj[u])
        if (--indeg[v] == 0) pq.push(v);
}

💡 Key insight. Uniqueness of topological order = the DAG has a Hamiltonian path. At every step exactly one node is available. This is equivalent to checking that the queue size never exceeds 1.

Uniqueness Trace

DAG: 1 → 2 → 3 → 4 (a chain)

Step	Heap	Size	Unique?
0	{1}	1	Yes
1	{2}	1	Yes
2	{3}	1	Yes
3	{4}	1	Yes

Unique: Yes.

Now add node 5 with no edges (isolated):

Step	Heap	Size	Unique?
0	{1, 5}	2	No
1	{2, 5}	2	No

We could put 5 before 1, between 1 and 2, etc. Multiple valid orderings.

Complexity

The min-heap adds a log factor:

Time: O((V + E) log V). Each push/pop on the heap costs O(log V). We do at most V pushes and V pops, plus E edge relaxations.
Space: O(V) for the heap and in-degree array.

For most problems, V and E are up to 2 * 10^5, so the log factor is negligible.

Try It

The starter code is set up for lex-smallest ordering. Fill in the heap operations.

Test case 1:

Input:
5 3
1 3
2 3
4 5

Output:
1 2 3 4 5

Test case 2:

Input:
4 2
2 1
3 4

Output:
2 1 3 4

Test case 3 -- cycle:

Input:
3 3
1 2
2 3
3 1

Output:
-1

Challenge: For the lex-largest topological order, would you use a max-heap? Yes. Think about why the same greedy argument applies in reverse.

Problems

Problem	Link	Difficulty
AtCoder abc223_d — Restricted Permutation	atcoder.jp/contests/abc223/tasks/abc223_d	Medium
AtCoder abc291_e — Find Permutation	atcoder.jp/contests/abc291/tasks/abc291_e	Medium
LC 210 — Course Schedule II	leetcode.com/problems/course-schedule-ii	Medium