My java DFS solution

  • 3

    See 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;
        for(Integer j:graph[i]){
               if(!dfs(j,visited,visiting,graph)) return false;
        return true;


  • 0

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

  • 0

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

  • 0

    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.

Log in to reply

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