207 Course Schedule

Leetcode

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.

等价于有向图是否存在还。构造一个图，然后用一个数组标记每个点是否没有访问、正在访问、访问过了。

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 0-unknown 1-visiting 2-visited
        int[] visited=new int[numCourses];
        ArrayList<Integer>[] graph=new ArrayList[numCourses];
        for(int i=0;i<numCourses;++i){
            graph[i]=new ArrayList<>();
        }
        
        for(int[] arr:prerequisites){
            graph[arr[0]].add(arr[1]);
        }
        
        for(int i=0;i<numCourses;++i){
            if(dfs(i, visited, graph)) return false;
        }
        return true;
    }
    // true-has circle
    private boolean dfs(int cur, int[] visited, ArrayList<Integer>[] graph){
        if(visited[cur]==1) return true;
        if(visited[cur]==2) return false;
        visited[cur]=1;
        for(int i:graph[cur]){
            if(dfs(i, visited, graph)) return true;
        }
        visited[cur]=2;
        return false;
    }
}