Simple java solution


  • 0
    H
    public class Solution {
        int[] visited;
        List<List<Integer>> courses;
        public boolean canFinish(int numCourses, int[][] prerequisites) {
            visited = new int[numCourses];
            courses = new ArrayList<List<Integer>>(numCourses);
            
            if(numCourses==0||prerequisites.length==0) return true;
            for(int i=0;i<numCourses;i++){
                courses.add(new ArrayList<Integer>());
            }
            
            int m = prerequisites.length;
            for(int i=0;i<m;i++){
                courses.get(prerequisites[i][0]).add(prerequisites[i][1]);
            }
            
            for(int i=0;i<numCourses;i++){
                if(!finishes(i)){
                   return false; 
                }
            }
            
            return true;
        }
        
        public boolean finishes(int i){
            if(visited[i] == -1) return false;
            if(visited[i] == 1) return true;
            
            visited[i] = -1;
            for(int j:courses.get(i)){
                if(!finishes(j)) return false;
            }
            visited[i] = 1;
            return true;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.