You are given a set of tasks and their prerequisites. Produce a valid execution order, or report that none exists.

The ordering and the cycle are the same question

A directed graph admits a linear order in which every edge points forwards exactly when it has no cycles. That equivalence is the first thing to say, because it tells the interviewer you understand why "detect a cycle" appears in the same breath as "give me an order": if three tasks each wait on the next, no sequence can put all three after their prerequisites, so a correct implementation must return a failure rather than an order that happens to look plausible.

Before any code, pin the edge direction down. Given the pair (a, b), does it mean a must run before b or a depends on b? They are transposes of each other and getting it backwards produces a perfectly valid topological order of the reversed graph, which is the exactly-wrong answer and passes no test. Say which convention you are using; interviewers phrase this problem loosely on purpose.

Kahn's method, where the cycle falls out of a counter

Maintain the in-degree of every node — its number of unmet prerequisites. Any node at zero is runnable now. Emit one, decrement the in-degree of each node it points to, and any that reaches zero becomes runnable in turn.

// adj.get(u) holds the nodes that may only run after u.
int[] topoOrder(int n, List<List<Integer>> adj) {
    int[] indegree = new int[n];
    for (List<Integer> edges : adj) {
        for (int v : edges) indegree[v]++;
    }

    Deque<Integer> ready = new ArrayDeque<>();
    for (int v = 0; v < n; v++) {
        if (indegree[v] == 0) ready.add(v);
    }

    int[] order = new int[n];
    int emitted = 0;
    while (!ready.isEmpty()) {
        int u = ready.poll();
        order[emitted++] = u;
        for (int v : adj.get(u)) {
            if (--indegree[v] == 0) ready.add(v);   // ready only when the LAST prerequisite clears
        }
    }

    return emitted == n ? order : null;             // a short order means a cycle swallowed the rest
}

The decrement is where the correctness lives. A node is enqueued at the moment its final incoming edge is retired, never earlier, so it can only be emitted after all of its prerequisites. The termination check is the cycle detector: nodes inside a cycle mutually hold each other's in-degree above zero, so none of them ever becomes ready and emitted stops short of n. You get detection for free rather than running a separate traversal, and n - emitted tells you how many nodes are in or downstream of a cycle.

Each node is enqueued and dequeued once and each edge is decremented once, so the running time is O(V + E) and the extra space is O(V) for the in-degree array and the queue.

The queue's discipline is unconstrained, which is worth noticing: the algorithm is correct with a stack, a FIFO queue, or anything else, because every node in it is legal to emit right now. That is also why the answer is generally not unique. If a specific order is wanted — the lexicographically smallest, say — replace the deque with a priority queue, which makes it O(E + V log V). Ask whether uniqueness matters instead of assuming, since a grader comparing against one expected array will fail a correct answer that chose a different valid order.

The DFS form, and the flag that is not enough

The alternative runs a depth-first search and appends each node to the output after all of its descendants have been finished, then reverses the result. A node's post-order position is later than everything reachable from it, so reversing puts it before all of them.

Cycle detection here needs three states per node, not two, and this is the detail that separates a working implementation from a subtly broken one. WHITE means untouched, GREY means on the current recursion stack, BLACK means finished. An edge to a GREY node is a back edge and therefore a cycle. An edge to a BLACK node is a forward or cross edge into a region already fully explored, which is completely legal.

private static final int WHITE = 0, GREY = 1, BLACK = 2;

// returns false if a cycle is found
private boolean visit(int u, List<List<Integer>> adj, int[] colour, Deque<Integer> out) {
    colour[u] = GREY;                                  // on the stack from here
    for (int v : adj.get(u)) {
        if (colour[v] == GREY) return false;           // back edge into the current path
        if (colour[v] == WHITE && !visit(v, adj, colour, out)) return false;
    }
    colour[u] = BLACK;                                 // off the stack, fully explored
    out.push(u);                                       // post-order push gives reversed order for free
    return true;
}

Collapse those three states into one boolean visited and the algorithm reports cycles that do not exist. Take the diamond 0 to 1, 0 to 2, 1 to 3, 2 to 3. Depth-first from 0 explores 1 then 3, unwinds, then explores 2 and finds 3 already visited. With only a boolean, "already visited" reads as a cycle; with three colours, 3 is BLACK and the edge is correctly ignored. The graph is acyclic and any diamond-shaped dependency — which is to say almost every real build graph — triggers the false positive.

Pushing onto a deque and popping it later, rather than appending and reversing, is a small convenience that removes one place to make an off-by-one error. The recursion is also the drawback: on a dependency chain of hundreds of thousands of nodes it overflows the stack, and Kahn's iterative form has no such limit, which is a reasonable tiebreaker when the input size is unbounded.

Undirected graphs need a different rule entirely

Do not carry the back-edge rule across. In an undirected graph every single edge appears from both endpoints, so u — v looks like a back edge from v to u the moment you arrive at v, and the grey check reports a cycle in a two-node tree. The fix is to ignore the edge you arrived by, tracking the parent, and then any other edge to an already-visited node is a genuine cycle. Union-find is the other standard answer and is often the cleaner one, because it processes edges in any order and needs no traversal at all. Note the parent-tracking version needs care in a multigraph: two parallel edges between the same pair are a cycle, so you must exclude the specific edge traversed rather than the parent node.

Topological order also does not exist as a concept for undirected graphs, which is why this question is always posed with a direction. If an interviewer describes symmetric relationships and asks for an ordering, that mismatch is itself the thing to raise.

Reporting the cycle rather than its existence

Being asked to name the offending tasks is the common follow-up, and it is easier in the DFS form. When you find the edge into a grey node, the cycle is the segment of the current recursion path from that node onwards, so keeping an explicit path list alongside the colours lets you slice it out directly. In Kahn's form the leftover nodes are those with a non-zero in-degree, which is the cycle plus everything downstream of it; recovering a minimal cycle from that set means one more traversal restricted to those nodes. Knowing which of the two algorithms answers which follow-up cheaply is a better signal than having memorised both.