Implement Topological Sort

The problem, simply

You get tasks numbered 0 to V - 1 and a list of one-way arrows. An arrow u > v means "do u before v". The arrows never go round in a loop.

Give back all the tasks in one line so that every arrow points forward: for every arrow u > v, u comes earlier in the line than v. Often many answers are correct; any one of them is fine.

A story to remember it

Picture it

Examples

Way 1: the simple way

Do exactly what the story says, the slow way. Keep a count of arrows coming into every task. Each round, look through all tasks for one that is not placed yet and has a count of 0.

1. Count incoming arrows for every task.
2. Repeat V times: scan all tasks for an unplaced one with count 0. If there is none, there is a loop.
3. Place it, and lower the count of every task it points to.

import java.util.*;

class Solution {
    public List<Integer> topoSort(int V, int[][] edges) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
        int[] in = new int[V];
        for (int[] e : edges) {
            adj.get(e[0]).add(e[1]);
            in[e[1]]++;
        }
        boolean[] placed = new boolean[V];
        List<Integer> order = new ArrayList<>();
        for (int round = 0; round < V; round++) {
            int pick = -1;
            for (int u = 0; u < V; u++) {          // scan everything, every round
                if (!placed[u] && in[u] == 0) { pick = u; break; }
            }
            if (pick == -1) return new ArrayList<>();   // nobody is free: a loop
            placed[pick] = true;
            order.add(pick);
            for (int v : adj.get(pick)) in[v]--;
        }
        return order;
    }
}

How long it takes: V rounds, and each round may scan all V tasks, plus each arrow is rubbed out once: O(V^2 + E). Extra room: the counts and flags, O(V). On the example it gives [4, 5, 0, 2, 3, 1], which is also correct.

Way 2: the clever way

Stop scanning. A task can only become free at the moment one of its incoming arrows is rubbed out. So keep a ready line, a queue, of tasks whose count is 0, and add a task to it the moment its count drops to 0.

1. Count incoming arrows for every task (its in-degree).
2. Put every task with count 0 in the ready line.
3. Take a task from the front and add it to the answer.
4. For every arrow going out of it, lower that task's count. If a count hits 0, that task joins the back of the line.
5. When the line is empty, check the answer has all V tasks. If not, there is a loop.

import java.util.*;

class Solution {
    public List<Integer> topoSort(int V, int[][] edges) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
        int[] in = new int[V];                       // arrows coming in
        for (int[] e : edges) {
            adj.get(e[0]).add(e[1]);
            in[e[1]]++;
        }
        Queue<Integer> ready = new ArrayDeque<>();
        for (int u = 0; u < V; u++) if (in[u] == 0) ready.add(u);
        List<Integer> order = new ArrayList<>();
        while (!ready.isEmpty()) {
            int u = ready.poll();
            order.add(u);
            for (int v : adj.get(u)) {
                if (--in[v] == 0) ready.add(v);      // its last blocker is gone
            }
        }
        if (order.size() < V) return new ArrayList<>();   // some tasks never got free: a loop
        return order;
    }
}

How long it takes: each task joins the line once and each arrow is rubbed out once, O(V + E). Extra room: the counts and the line, O(V).

Another way: depth first search

Dive from every unseen task, like a cave explorer. When a task has no more unseen tasks after it, it is finished: everything that must come after it is already finished. Write finished tasks on a list. The list is the answer backwards, so reverse it at the end.

import java.util.*;

class Solution {
    public List<Integer> topoSort(int V, int[][] edges) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) adj.get(e[0]).add(e[1]);
        boolean[] seen = new boolean[V];
        List<Integer> finished = new ArrayList<>();
        for (int u = 0; u < V; u++) if (!seen[u]) dive(adj, u, seen, finished);
        Collections.reverse(finished);               // last finished goes first
        return finished;
    }

    private void dive(List<List<Integer>> adj, int u, boolean[] seen, List<Integer> finished) {
        seen[u] = true;
        for (int v : adj.get(u)) if (!seen[v]) dive(adj, v, seen, finished);
        finished.add(u);                             // everything after u is done
    }
}

On the example, tasks finish in the order 0, 1, 3, 2, 4, 5, so the answer is [5, 4, 2, 3, 1, 0]. It is also O(V + E). This version assumes there is no loop; to catch one, keep a third mark for "still on the current dive" and report a loop if you meet such a task.

Watch out for

• Getting the arrow direction backwards. Decide once: u > v means u first, and count arrows into v.
• Adding a task to the ready line more than once. Only add it when its count goes from 1 to 0.
• Forgetting tasks with no arrows at all. They still have count 0 and must be in the answer.
• Expecting one fixed answer. Many orders are valid; if the judge wants the smallest one in dictionary order, use a min-heap instead of a plain queue.

What interviewers ask next

• Course schedule: can you finish all courses? Run Kahn's algorithm and check whether all V courses got placed.
• The smallest order in dictionary order? Replace the queue with a priority queue that always gives the smallest free task. That costs O(V log V + E).
• Is the order unique? It is unique exactly when the ready line never holds more than one task at a time.
• Fewest semesters to finish, if you can take any number of free courses at once? Process the line one whole layer at a time and count the layers.
• Why must there be no loop? In a loop every task waits for another one in the loop, so none can go first.

Remember this

Grown-up words: tasks are vertices, arrows are directed edges, a graph with no loops is a DAG (directed acyclic graph), the count of arrows coming in is the in-degree, the ready line is a queue, and this method is Kahn's algorithm. The order itself is a topological sort.