Course Schedule

1package pkg5leetcode.blind75;2 3/*4 * Course Schedule | LC 2075 * APPROACH: Kahn topological sort detects cycle in directed graph.6 * COMPLEXITY: Time O(V+E), Space O(V+E)7 */8import java.util.*;9 10public class blind75_LC207CourseSchedule {11    static boolean canFinish(int numCourses, int[][] prerequisites) {12        List<List<Integer>> adj = new ArrayList<>();13        int[] indeg = new int[numCourses];14        for (int i = 0; i < numCourses; i++) adj.add(new ArrayList<>());15        for (int[] p : prerequisites) {16            adj.get(p[1]).add(p[0]);17            indeg[p[0]]++;18        }19        Deque<Integer> q = new ArrayDeque<>();20        for (int i = 0; i < numCourses; i++) if (indeg[i] == 0) q.add(i);21        int seen = 0;22        while (!q.isEmpty()) {23            int u = q.poll();24            seen++;25            for (int v : adj.get(u)) if (--indeg[v] == 0) q.add(v);26        }27        return seen == numCourses;28    }29 30    public static void main(String[] args) {31        check(canFinish(2, new int[][]{{1, 0}}), "case1");32        check(!canFinish(2, new int[][]{{1, 0}, {0, 1}}), "case2");33        System.out.println("all tests passed");34    }35 36    static void check(boolean cond, String name) {37        if (!cond) throw new AssertionError("FAILED: " + name);38        System.out.println("  PASS " + name);39    }40}