Java DFS Simple 98.50% code


  • 0
    Z
    public boolean canFinish(int numCourses, int[][] prerequisites) {
    	boolean[] visited = new boolean[numCourses], path = new boolean[numCourses];
    	List<Integer>[] nextCourses = new ArrayList[numCourses];
    	for (int[] pre : prerequisites) {   // transform list of edges to map
    		if (nextCourses[pre[1]] == null) nextCourses[pre[1]] = new ArrayList<>();
    		nextCourses[pre[1]].add(pre[0]);
    	}
    	for(int i = 0; i < numCourses; i++) {
    		if(hasCycle(nextCourses, visited, path, i)) return false;
    	}
    	return true;
    }
    private boolean hasCycle(List<Integer>[] nextCourses, boolean[] visited, boolean[] path, int course) {
    	if(path[course]) return true;               // visited before by this dfs
    	if(visited[course] || nextCourses[course] == null) return false; // until the end or visited before
    	visited[course] = true;
    	path[course] = true;
    	for(int child : nextCourses[course]) {
    		if(hasCycle(nextCourses, visited, path, child)) {
    			path[course] = false;
    			return true;
    		}
    	}
    	path[course] = false;
    	return false;
    }
    

Log in to reply
 

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