Topological Sort: What Comes First?

Getting dressed

Socks before shoes, shirt before tie, trousers before shoes. Any order that respects every “before” rule is a topological order. The rules form a directed graph: an arrow A → B means A comes first.

Kahn's algorithm

• Count each task's in-degree: how many arrows point at it (how many tasks must come first).
• Tasks with in-degree 0 are ready – put them in a queue.
• Take a ready task, add it to the order, and remove its arrows: each task it pointed at loses 1 from its in-degree. Any that drop to 0 become ready.
• If some tasks never become ready, the rules have a loop – no valid order exists.

import java.util.ArrayDeque;
import java.util.ArrayList;

public class Main {
    public static void main(String[] args) {
        String[] task = {"", "underwear", "trousers", "socks", "shoes", "shirt", "belt"};
        int n = 6;
        int[][] before = {{1, 2}, {2, 4}, {3, 4}, {2, 6}, {5, 6}};   // a must come before b
        ArrayList<ArrayList<Integer>> g = new ArrayList<ArrayList<Integer>>();
        for (int i = 0; i <= n; i++) g.add(new ArrayList<Integer>());
        int[] inDegree = new int[n + 1];
        for (int[] r : before) {
            g.get(r[0]).add(r[1]);
            inDegree[r[1]]++;
        }

        ArrayDeque<Integer> ready = new ArrayDeque<Integer>();
        for (int i = 1; i <= n; i++) if (inDegree[i] == 0) ready.offer(i);
        int done = 0;
        while (!ready.isEmpty()) {
            int t = ready.poll();
            System.out.println(++done + ". " + task[t]);
            for (int next : g.get(t)) {
                inDegree[next]--;
                if (inDegree[next] == 0) ready.offer(next);
            }
        }
        if (done < n) System.out.println("impossible: the rules contain a loop");
    }
}

Output

1. underwear
2. socks
3. shirt
4. trousers
5. shoes
6. belt

Tip: There can be many valid orders. If you need one exact answer – for example “always pick the smallest number that's ready” – use a PriorityQueue instead of the plain queue.

Remember: Topological sort only works on directed graphs with no loops (called DAGs). O(n + m).