Topological Sorting

A topological order of a directed graph places every edge u → v with u before v. Such an order exists exactly when the graph is acyclic.

Kahn's algorithm

1. Compute every vertex's in-degree.
2. Queue all vertices of in-degree zero.
3. Remove one, append it to the order, and decrement its neighbors' in-degrees.
4. Queue neighbors whose in-degree becomes zero.
5. If fewer than V vertices were emitted, a directed cycle exists.

static List<Integer> topologicalOrder(List<List<Integer>> graph) {
    int[] indegree = new int[graph.size()];
    for (List<Integer> edges : graph) {
        for (int target : edges) indegree[target]++;
    }
    Queue<Integer> ready = new ArrayDeque<>();
    for (int v = 0; v < indegree.length; v++) if (indegree[v] == 0) ready.add(v);

    List<Integer> order = new ArrayList<>();
    while (!ready.isEmpty()) {
        int vertex = ready.remove();
        order.add(vertex);
        for (int target : graph.get(vertex)) {
            if (--indegree[target] == 0) ready.add(target);
        }
    }
    if (order.size() != graph.size()) {
        throw new IllegalArgumentException("graph contains a directed cycle");
    }
    return order;
}

Every emitted vertex currently has no incoming edge from remaining vertices, so placing it next is safe. The algorithm takes Θ(V + E) time and Θ(V) auxiliary space. Orders are generally not unique; a priority queue can choose a canonical smallest available vertex at additional logarithmic cost.