[daily training] 207 Class Schedule Card

subject

You must take this semester numCourses Courses , Write it down as 0 To numCourses - 1 .

Before you take some courses, you need some prerequisite courses . Prerequisite courses by array prerequisites give , among prerequisites[i] = [ai, bi] , If you want to learn a course ai be must Learn the course first bi .

for example , The prerequisite course is right for [0, 1] Express ： Want to learn the course 0 , You need to finish the course first 1 .
Please judge whether it is possible to complete all the courses ？ If possible , return true ; otherwise , return false .

Example 1：
Input ：numCourses = 2, prerequisites = [[1,0]]
Output ：true
explain ： All in all 2 Courses . Study the course 1 Before , You need to complete the course 0 . It's possible .

Example 2：
Input ：numCourses = 2, prerequisites = [[1,0],[0,1]]
Output ：false
explain ： All in all 2 Courses . Study the course 1 Before , You need to finish ​ Course 0 ; And study the course 0 Before , You should also finish the course first 1 . It's impossible .

Tips ：
1 <= numCourses <= 10⁵
0 <= prerequisites.length <= 5000
prerequisites[i].length == 2
0 <= ai, bi < numCourses
prerequisites[i] All the courses in are right Different from each other

Code

package dayLeetCode;

import java.util.ArrayList;
import java.util.List;

public class dayleetcode207 {
    
    // dfs 

    //  Connect the account with its predecessor 
    List<List<Integer>> list = new ArrayList<>();
    //  Tag array ,0  Not searched , 1  Searching , 2  Search complete 
    int visited[];
    //  Mark whether there is a ring , A ring must be false
    boolean flag = true;

    public boolean canFinish(int numCourses, int[][] prerequisites) {
    
        //  initialization 
        visited = new int[numCourses];
        for (int i = 0; i < numCourses; i++){
    
            list.add(new ArrayList<Integer>());
        }

        for (int num[] : prerequisites){
    
            //  learn num[0]  Before   Want to learn num[1], So let num[1] Point to num[0]
            list.get(num[0]).add(num[1]);
        }

        for (int i = 0; i < numCourses; i++){
    
            if (visited[i]== 0){
    
                dfs(i);
            }
        }
        return flag;
    }

    private void dfs(int k) {
    
        visited[k] = 1;
        //  To study subjects k Words , Need to finish list.get(k) These front accounts 
        for (int t : list.get(k)){
    
            //  If the subject pointed to has not been searched, search deeply 
            if (visited[t] == 0){
    
                dfs(t);
                // Determine whether the lower level search has a ring 
                if (!flag){
    
                    return;
                }
            }
            //  An account pointed to is in search , Generate rings 
            else if (visited[t] == 1){
    
                flag = false;
                return;
            }
        }
        //  Search complete , Mark as searched , Learning is over 
        visited[k] = 2;

    }

    public static void main(String[] args) {
    
        dayleetcode207 obj = new dayleetcode207();
        System.out.println(obj.canFinish(2, new int[][]{
    {
    1, 0}}));
    }
}