207. Course Schedule - pangeneral/leetcode-notebook GitHub Wiki

This problem is searching the rings in bidirectional graph, which can be solved via topological sort or dfs. I solve it through dfs and the basic idea is using a array used to denote the state of node:

  1. used[i] = 0, the node has no been visited;
  2. used[i] = 1, the node has been visited;
  3. used[i] = -1, the node is under visiting;

During dfs, if we find a node under visited, then a ring exists.

public boolean canFinish(int numCourses, int[][] prerequisites) {
    List<List<Integer>> courseToPre = new ArrayList<List<Integer>>();
    for (int i = 0; i < numCourses; i++) 
        courseToPre.add(new ArrayList<Integer>());
    for (int i = 0; i < prerequisites.length; i++) 
        courseToPre.get(prerequisites[i][0]).add(prerequisites[i][1]);

    int used[] = new int[numCourses];
    for (int i = 0; i < numCourses; i++) {
        if (used[i] == 0 && !traverse(courseToPre, i, used))
            return false;
    }
    return true;
}

public boolean traverse(List<List<Integer>> courseToPre, int index, int used[]) {
    used[index] = -1; // node is under visiting
    List<Integer> preList = courseToPre.get(index);
    for (int i = 0; i < preList.size(); i++) {
        int next = preList.get(i);
        if (used[next] == 1) // the node has been visited
            continue;
        if (used[preList.get(i)] == -1 || !traverse(courseToPre, preList.get(i), used))
            return false;
    }
    used[index] = 1; // visit finish
    return true;
}
⚠️ **GitHub.com Fallback** ⚠️