java solution using dfs (beating 92.14%)


  • 0
    D

    My code reference to Algorithms (Robert Sedgewick)

    public boolean canFinish(int numCourses, int[][] prerequisites) {
    		List<Integer> graph[] = new ArrayList[numCourses];
    		for (int i = 0; i < numCourses; i++){
    			graph[i] = new ArrayList<>();
    		}
    		boolean[] visited = new boolean[numCourses];
    		boolean[] onStack = new boolean[numCourses];
    		for (int[] pre : prerequisites){
    			graph[pre[0]].add(pre[1]);
    		}
    		
    		isCycle = false;
    		for (int i = 0; i < numCourses; i++){
    			if (!visited[i]){
    				dfs(graph, i, visited, onStack);
    			}
    		}
    		return !hasCycle();
    	}
    	
    	private void dfs(List<Integer> g[], int v,boolean[] visited, boolean[] onStack){
    		visited[v] = true;
    		onStack[v] = true;
    		for (int w : g[v]){
    			if (this.hasCycle()) return;
    			if (!visited[w]) dfs(g, w, visited, onStack);
    			else if (onStack[w]){
    				isCycle = true;
    			}
    		}
    		onStack[v] = false;
    	}
    	
    	boolean isCycle = false;
    	private boolean hasCycle(){
    		return isCycle;
    	}
    

    Once the vertex w is visited and dfs(w) has no cycle. The second time when we visit other node from h to w, visited[w] is true, so the next time to dfs(w) can be avoided. But we need another state to memorize the vertex we have visited in one dfs. So it's onStack, it can be restored when dfs return. By this way we can detect cycle if it visit one vertex twice.


Log in to reply
 

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