# 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

```java
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

```java
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;
    }
}
```
