Understadable DFS Method


  • 0
    Z

    // 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:

    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;
    }
    }


Log in to reply
 

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