0207. Course Schedule

https://leetcode.com/problems/course-schedule

Description

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

• For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.

Return true if you can finish all courses. Otherwise, return false.

Example 1:

**Input:** numCourses = 2, prerequisites = [[1,0]]
**Output:** true
**Explanation:** There are a total of 2 courses to take. 
To take course 1 you should have finished course 0. So it is possible.

Example 2:

**Input:** numCourses = 2, prerequisites = [[1,0],[0,1]]
**Output:** false
**Explanation:** There are a total of 2 courses to take. 
To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

Constraints:

• 1 <= numCourses <= 105

• 0 <= prerequisites.length <= 5000

• prerequisites[i].length == 2

• 0 <= ai, bi < numCourses

• All the pairs prerequisites[i] are unique.

ac1: Topological + BFS

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        if (numCourses <= 0) return false;

        // have a graph
        List<List<Integer>> adjList = new ArrayList<List<Integer>>();
        for (int i = 0; i < numCourses; i++) {
            adjList.add(new ArrayList<Integer>());
        }

        // get indegree
        int[] indegree = new int[numCourses];
        for (int[] pre : prerequisites) {
            indegree[pre[0]]++;
            adjList.get(pre[1]).add(pre[0]);
        }

        // BFS
        Queue<Integer> q = new LinkedList<Integer>();
        for (int i = 0; i < indegree.length; i++) {
            if (indegree[i] == 0) q.offer(i);
        }
        while (!q.isEmpty()) {
            int head = q.poll();
            for (int next : adjList.get(head)) {
                indegree[next]--;
                if (indegree[next] == 0) {
                    q.offer(next);
                }
            }
        }

        // Determine
        for (int inde : indegree) {
            if (inde != 0) return false;
        }

        return true;
    }
}

ac2: Graph + DFS

spend too much time

class Solution {
    private boolean[] onStack;
    private Set<Integer> visited;
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        if (numCourses <= 0) return false;

        // have a graph
        List<List<Integer>> adjList = new ArrayList<List<Integer>>();
        onStack = new boolean[numCourses];
        visited = new HashSet<Integer>();
        for (int i = 0; i < numCourses; i++) {
            adjList.add(new ArrayList<Integer>());
        }
        for (int[] pre : prerequisites) {
            adjList.get(pre[1]).add(pre[0]);
        }

        for (int i = 0; i < numCourses; i++) {
            if (!visited.contains(i) && hasCycle(adjList, i)) return false;
        }

        return true;
    }

    private boolean hasCycle(List<List<Integer>> adjList, int s) {
        visited.add(s);
        onStack[s] = true;
        for (int w : adjList.get(s)) {
            if (onStack[w] || hasCycle(adjList,w)) return true;
        }
        onStack[s] = false;
        return false;
    }
}