Leetcode 207: course schedule (topological sorting determines whether the loop is formed)

LeetCode 207

subject ：

Ideas ：

notice Dependence problem , First of all, I want to turn the problem into Directed graph ！

1. Use conditions to build diagrams , Course is the apex , A few nodes have several vertices , Set up in numbers List[ ] Array representation diagram , The index of the array is the value of the vertex , Each element of the array is the adjacency table corresponding to the vertex ;
   Use the lessons learned first pre Point to post learning courses follow To represent the order of directed graphs
2. main Use the first in for Traverse every vertex of the graph , Use... For the adjacency table of vertices dfs
3. stay dfs Use the second in for Traverse the adjacency table of the vertex
   When onpath True marks isCycle by true
   Be careful for Restore after completion onpath=false

Be careful ：
For the convenience of memory , When onpath[s]=true and marked[s]=true directly return

Java Realization ：

class Solution {
    
    boolean[] marked;
    boolean[] onPath;
    boolean isCycle=false;

    public boolean canFinish(int numCourses, int[][] prerequisites) {
    
        //  It's impossible to complete ：  There is cyclic dependence , Mutual presupposition ,  You can't finish the course 
        // Build a diagram 
        List<Integer>[] graph=buildGraph(numCourses,prerequisites);
        // initialization 
        marked=new boolean[numCourses];
        onPath=new boolean[numCourses];
    
        // use dfs Traverse every vertex 
        for(int i=0;i<numCourses;i++){
    
            dfs(graph,i);           
        }
        return !isCycle;// Learning can be completed without forming a circle 
    }
    	
        List<Integer>[] buildGraph(int numCourses,int[][]prerequisites){
    
            List<Integer>[] graph=new List[numCourses];//graph Elements are arrays ！
            // Initialize each element ：new One List As adjacency table 
            for(int i=0;i<numCourses;i++){
    
                graph[i]=new LinkedList<>();
            }
            // Add directed edges 
            for(int[] k:prerequisites){
    
                int pre=k[1];
                int follow=k[0];
                graph[pre].add(follow); // graph The index of corresponds to the value of the vertex ,
            }
            return graph;
        }
    }
    
        void dfs(List<Integer>[] graph,int s){
    
            // Termination conditions 
            if(onPath[s]==true){
    
                isCycle=true;
                return;
            }
            if(marked[s]==true){
    
                return;
            }
            marked[s]=true;// Mark current s
            onPath[s]=true;// Mark onpath
            // Traverse adjacency table 
            for(int k:graph[s]){
    
                    dfs(graph,k);
            }
            onPath[s]=false;//onpath Restore 
        }