Topological Sort

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

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

    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < n; i++)
        if (inDegree[i] == 0) queue.offer(i); // start with nodes with no deps

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

    return idx == n ? order : new int[0]; // empty if cycle detected
}

// LeetCode 207
public boolean canFinish(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);
    int completed = 0;
    while (!queue.isEmpty()) {
        int course = queue.poll();
        completed++;
        for (int next : adj.get(course))
            if (--inDegree[next] == 0) queue.offer(next);
    }
    return completed == numCourses;
}

public List<Integer> topologicalSortDFS(int n, List<List<Integer>> adj) {
    boolean[] visited = new boolean[n];
    boolean[] inStack = new boolean[n];
    Deque<Integer> stack = new ArrayDeque<>();
    boolean[] hasCycle = {false};

    for (int i = 0; i < n; i++)
        if (!visited[i]) dfs(adj, i, visited, inStack, stack, hasCycle);

    if (hasCycle[0]) return Collections.emptyList();
    List<Integer> result = new ArrayList<>();
    while (!stack.isEmpty()) result.add(stack.pop());
    return result;
}

void dfs(List<List<Integer>> adj, int node, boolean[] visited,
         boolean[] inStack, Deque<Integer> stack, boolean[] hasCycle) {
    visited[node] = true;
    inStack[node] = true;
    for (int neighbor : adj.get(node)) {
        if (!visited[neighbor]) dfs(adj, neighbor, visited, inStack, stack, hasCycle);
        else if (inStack[neighbor]) hasCycle[0] = true;
    }
    inStack[node] = false;
    stack.push(node); // add to result AFTER processing all neighbors
}

// Given sorted alien words, find the character ordering
// Build a graph: if words[i][j] != words[i+1][j], then words[i][j] comes before words[i+1][j]
// Then topological sort the character graph