CourseScheduleII_210.java

/*
    Original problem from LeetCode: Course Schedule II
    Leetcode Link: https://leetcode.com/problems/course-schedule-ii/
*/

// Approach-1 (Using BFS Topological Sort Concept)
import java.util.*;

class Solution {
    // Using Kahn's algorithm
    private List<Integer> topologicalSortCheck(Map<Integer, List<Integer>> adj, int n, int[] indegree) {
        Queue<Integer> queue = new LinkedList<>();
        int count = 0;
        List<Integer> result = new ArrayList<>();
        
        for (int i = 0; i < n; i++) {
            if (indegree[i] == 0) {
                result.add(i);
                count++;
                queue.offer(i);
            }
        }
        
        while (!queue.isEmpty()) {
            int u = queue.poll();
            
            if (adj.containsKey(u)) {
                for (Integer v : adj.get(u)) {
                    indegree[v]--;
                    
                    if (indegree[v] == 0) {
                        result.add(v);
                        count++;
                        queue.offer(v);
                    }
                }
            }
        }
        
        if (count != n)
            return new ArrayList<>();
        
        return result;
    }
    
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        Map<Integer, List<Integer>> adj = new HashMap<>();
        
        int[] indegree = new int[numCourses]; // for Kahn's algo
        
        for (int[] prerequisite : prerequisites) {
            int a = prerequisite[0];
            int b = prerequisite[1];
            
            // b ---> a
            adj.computeIfAbsent(b, k -> new ArrayList<>()).add(a);
            
            // arrow points to 'a'
            indegree[a]++;
        }
        
        List<Integer> resultList = topologicalSortCheck(adj, numCourses, indegree);
        
        // Convert List<Integer> to int[]
        int[] result = new int[resultList.size()];
        for (int i = 0; i < resultList.size(); i++) {
            result[i] = resultList.get(i);
        }
        
        return result;
    }
}

// Approach-2 (Using DFS)
class Solution2 {
    private boolean hasCycle = false;
    
    private void DFS(Map<Integer, List<Integer>> adj, int u, boolean[] visited, Stack<Integer> st, boolean[] inRecursion) {
        visited[u] = true;
        inRecursion[u] = true;
        
        // First process all children of 'u'
        if (adj.containsKey(u)) {
            for (Integer v : adj.get(u)) {
                if (inRecursion[v]) {
                    hasCycle = true;
                    return;
                }
                
                if (!visited[v])
                    DFS(adj, v, visited, st, inRecursion);
            }
        }
        
        // Now add 'u' to the stack
        st.push(u);
        inRecursion[u] = false;
    }
    
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        Map<Integer, List<Integer>> adj = new HashMap<>();
        boolean[] visited = new boolean[numCourses];
        boolean[] inRecursion = new boolean[numCourses];
        hasCycle = false;
        
        Stack<Integer> st = new Stack<>();
        
        for (int[] prerequisite : prerequisites) {
            int a = prerequisite[0];
            int b = prerequisite[1];
            
            // b--->a
            adj.computeIfAbsent(b, k -> new ArrayList<>()).add(a);
        }
        
        for (int i = 0; i < numCourses; i++) {
            if (!visited[i])
                DFS(adj, i, visited, st, inRecursion);
        }
        
        if (hasCycle)
            return new int[0];
        
        int[] result = new int[numCourses];
        int index = 0;
        
        while (!st.isEmpty()) {
            result[index++] = st.pop();
        }
        
        return result;
    }
}