My java DFS solution


  • 3
    Y

    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++){
            graph[prerequisites[i][1]].add(prerequisites[i][0]);
        }
        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;
    }
    

    }


  • 0
    B

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


  • 0
    Q

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


  • 0
    5

    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.