My java DFS solution

• See http://en.wikipedia.org/wiki/Topological_sorting for the algorithm.

``````public class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
if(prerequisites==null||prerequisites.length==0) return true;
int n=numCourses;
HashSet<Integer>[] graph=new HashSet[n];
for(int i=0;i<n;i++) graph[i]=new HashSet<>();
for(int i=0;i<prerequisites.length;i++){
}
boolean[] visited=new boolean[n];
boolean[] visiting=new boolean[n];
for(int i=0;i<n;i++){
if(!visited[i]) {
if(!dfs(i,visited,visiting,graph)) return false;
}
}
return true;
}

public boolean dfs(int i,boolean[] visited,boolean[] visiting, HashSet<Integer>[] graph){
if(visiting[i]) return false;
visiting[i]=true;
for(Integer j:graph[i]){
if(!visited[j]){
if(!dfs(j,visited,visiting,graph)) return false;
}
}
visiting[i]=false;
visited[i]=true;
return true;
}
``````

}

• So `visited[]` is what we had already taken; `visiting[]` is what we are not sure yet, like just "booked", right?

• visiting[] is used for cycle checked. visited[] is used so that we don't check the same path twice.

• I would suggest in the beginning of dfs, add one line
if (visited[i]) return true;

Otherwise the algorithm is not as efficient. Suppose when doing the loop when meet the lower level nodes first and then upper level nodes. Then there would be a lot of repeating work.

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