lc-207

/**
 * There are a total of numCourses courses you have to take, labeled from 0 to
 * numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai,
 * bi] indicates that you must take course bi first if you want to take course ai.
 * <p>
 * <p>
 * For example, the pair [0, 1], indicates that to take course 0 you have to
 * first take course 1.
 * <p>
 * <p>
 * Return true if you can finish all courses. Otherwise, return false.
 * <p>
 * <p>
 * Example 1:
 * <p>
 * <p>
 * Input: numCourses = 2, prerequisites = [[1,0]]
 * Output: true
 * Explanation: There are a total of 2 courses to take.
 * To take course 1 you should have finished course 0. So it is possible.
 * <p>
 * <p>
 * Example 2:
 * <p>
 * <p>
 * Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
 * Output: false
 * Explanation: There are a total of 2 courses to take.
 * To take course 1 you should have finished course 0, and to take course 0 you
 * should also have finished course 1. So it is impossible.
 * <p>
 * <p>
 * <p>
 * Constraints:
 * <p>
 * <p>
 * 1 <= numCourses <= 2000
 * 0 <= prerequisites.length <= 5000
 * prerequisites[i].length == 2
 * 0 <= ai, bi < numCourses
 * All the pairs prerequisites[i] are unique.
 * <p>
 * Related Topics深度优先搜索 | 广度优先搜索 | 图 | 拓扑排序
 * <p>
 * 👍 1422, 👎 0
 */
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    private List<List<Integer>> edges;

    private int[] visited;

    private boolean valid = true;

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        edges = new ArrayList<>();

        for (int i = 0; i < numCourses; i++) {
            edges.add(new ArrayList<>());
        }

        visited = new int[numCourses];

        for (int[] pre : prerequisites) {
            edges.get(pre[1]).add(pre[0]);
        }

        for (int i = 0; i < numCourses; i++) {
            this.valid = dfs(i);
            if (!this.valid) {
                break;
            }
        }

        return this.valid;
    }


    private boolean dfs(int u) {
        visited[u] = 1;

        for (int v : edges.get(u)) {
            if (visited[v] == 0) {
                this.valid = dfs(v);
                if (!this.valid) {
                    break;
                }
            } else if (visited[v] == 1) {
                this.valid = false;
                break;
            }
        }

        visited[u] = 2;

        return this.valid;
    }
}
//leetcode submit region end(Prohibit modification and deletion)