Understandable DFS Way


  • 1
    Z
     public class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        if (prerequisites.length == 0) return true;
        int[] visit = new int[numCourses];        // 0: unvisited, 1: visiting, 2: visited
        for (int i = 0; i < prerequisites.length; i++){
            if (visit[prerequisites[i][1]] == 0){
                boolean classPath = dfs(prerequisites, visit, prerequisites[i][1]);
                if (classPath == false) return false;
            }
        }
        return true;
    }
    private boolean dfs(int[][] prerequisites, int[] visit, int precourse){
        if (visit[precourse] == 1) return false;
        if (visit[precourse] == 2) return true;
        visit[precourse] = 1;
        for (int i = 0; i < prerequisites.length; i++){
            if (prerequisites[i][1] == precourse){
                //System.out.println(precourse);
                boolean nextPath =  dfs(prerequisites, visit, prerequisites[i][0]);
                if (!nextPath) return false;
            }
        }
        visit[precourse] = 2;
        return true;
    }
    

    }

    //// Introduce 3 status for a Node: unvisited, visiting, visited
    // Visiting means a Node is in the current DFS Path.
    // Change visiting node to be visited when the DFS path ends.
    // This marking way helps a lot when we do DFS:


Log in to reply
 

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