Course Schedule I / II unified: detect cycle and produce order

• Unified approach runs a single Kahn's-algorithm pass that serves both Course Schedule variants.
• Course Schedule I returns whether the emitted count equals the total (boolean feasibility).
• Course Schedule II returns the emitted order when complete, or an empty array on cycle detection.
• Emitted-count check is the single source of truth for both cycle detection and order validity.
• DRY principle avoids writing two separate traversals for what is fundamentally one algorithm.
• Time is O(V + E); space is O(V + E).

What is the unified Course Schedule approach?

Course Schedule I asks "can all courses be finished?" and Course Schedule II asks "in what order?" Both are answered by a single Kahn's-algorithm pass. The key insight is that the boolean feasibility answer is a byproduct of the order construction: if the emitted count equals the total, all courses are finishable, and the emitted sequence is the valid order.

package com.bank.service;

import java.util.*;

public class UnifiedScheduleService {
    private int[] order;
    private boolean feasible;

    public void solve(int numCourses, int[][] prerequisites) {
        List<List<Integer>> adj = new ArrayList<>();
        int[] inDegree = new int[numCourses];
        for (int i = 0; i < numCourses; i++) adj.add(new ArrayList<>());

        for (int[] pre : prerequisites) {
            adj.get(pre[1]).add(pre[0]);
            inDegree[pre[0]]++;
        }

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) queue.offer(i);
        }

        order = new int[numCourses];
        int idx = 0;
        while (!queue.isEmpty()) {
            int course = queue.poll();
            order[idx++] = course;
            for (int next : adj.get(course)) {
                if (--inDegree[next] == 0) queue.offer(next);
            }
        }

        feasible = (idx == numCourses);
        if (!feasible) order = new int[0];
    }

    // Course Schedule I answer
    public boolean canFinish() { return feasible; }

    // Course Schedule II answer
    public int[] findOrder() { return order; }
}

Why should you implement this as a single algorithm?

Writing two separate traversals for what is the same algorithm creates duplicated logic that can drift apart. A bug fix in one might be missed in the other. By implementing the ordering variant and deriving the boolean from the emitted-count check, you keep the code DRY and the two answers consistent.

// Two answers from one pass:
boolean canFinish = (idx == numCourses);  // Course Schedule I
int[] order = canFinish ? emittedOrder : new int[0];  // Course Schedule II

How does the emitted-count check work as the single source of truth?

Kahn's algorithm processes every node that can be reached without going through a cycle. If the graph is acyclic, every node gets processed, and the count equals the total. If a cycle exists, the cycle's nodes can never reach zero in-degree, so they are never processed, and the count falls short.

Acyclic graph:    0 → 1 → 2
Processed: 0, 1, 2   Count = 3 == total → feasible, order = [0,1,2]

Cyclic graph:     0 → 1 → 2 → 0
Processed: (none, all have in-degree >= 1)
Count = 0 < 3 → not feasible, order = []

How does this compare to separate DFS implementations?

DFS can also answer both questions. The finish order reversed is a topological order, and a back edge detected during DFS indicates a cycle. However, combining both checks in a single DFS requires careful three-color marking plus order recording, which is more error-prone than Kahn's straightforward approach.

| Aspect | Unified Kahn's | Separate DFS for I and II |
|--------|---------------|---------------------------|
| Code duplication | None | Risk of divergence |
| Cycle detection | Implicit (count check) | Explicit (back edge) |
| Order production | Direct (emitted sequence) | Reverse finish order |
| Simplicity | Higher | Lower |

What are edge cases?

• Zero courses: both return trivially (feasible = true, order = []).
• No prerequisites: all courses have in-degree 0, any order is valid.
• All courses in a single cycle: count = 0, not feasible.
• Multiple disconnected components: each is handled independently by Kahn's.

// Edge case: no prerequisites
// All in-degrees are 0, all enqueued at once
// Any processing order is valid

What are common mistakes?

The first mistake is implementing Course Schedule I and II as completely separate algorithms, missing the opportunity to share logic. The second is returning the partial order array instead of an empty array when a cycle is detected. The third is assuming a specific queue ordering matters for correctness.

// WRONG: returns partial order on cycle
return order;  // may contain only some courses

// CORRECT: returns empty on cycle
return feasible ? order : new int[0];

What about multiple valid orders?

Topological ordering is not unique in general. The specific order depends on which zero-in-degree node the queue produces first. Using a min-heap instead of a regular queue would produce the lexicographically smallest order, which some problems require.

// Regular queue: arbitrary valid order
Queue<Integer> queue = new LinkedList<>();

// Min-heap: lexicographically smallest valid order
Queue<Integer> queue = new PriorityQueue<>();

What should a senior engineer know?

At the National Bank of India, a regulatory-filing workflow needed both a confirmation that all filings could be completed and the actual filing order. One Kahn's pass served both: the emitted order was the schedule, and the emitted-count check was the feasibility verdict. A single well-tested routine answered both questions, and a dependency cycle produced a clean negative with an empty order rather than a half-built plan. The senior design point is recognizing that both variants are the same problem and writing one tested solution instead of two fragile ones.