Java 5ms Solutions using DFS and recursion


  • 1
    R
    public static boolean canFinish(int numCourses, int[][] prerequisites) {
    	ArrayList<Integer>[] map = new ArrayList[numCourses]; /*
    															 * map of all
    															 * prerequisites
    															 * and the
    															 * courses that
    															 * should be
    															 * taken after
    															 * them
    															 */
    	for (int i = 0; i < numCourses; i++) {
    		map[i] = new ArrayList<Integer>();
    	}
    	for (int i = 0; i < prerequisites.length; i++) { // pre -> vertex
    		map[prerequisites[i][1]].add(prerequisites[i][0]);
    	}
    	int[] visitState = new int[numCourses];
    	Arrays.fill(visitState, 0); // 0: unvisited, 1: visiting, 2:visited
    
    	for (int i = 0; i < numCourses; i++) {
    		if (!DFSVisit(i, map, visitState))
    			return false;
    	}
    	return true;
    }
    
    private static boolean DFSVisit(int n, ArrayList<Integer>[] map, int[] visitState) {
    	if (visitState[n] == 2)
    		return true;
    	if (visitState[n] == 1)
    		return false;
    
    	visitState[n] = 1;
    	for (int j = 0; j < map[n].size(); j++) {
    		if (!DFSVisit(map[n].get(j), map, visitState))
    			return false;
    	}
    	visitState[n] = 2;
    	return true;
    }

Log in to reply
 

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