public class canFinish_207 {
    
    // ================= 思路 1：BFS（拓扑排序） =================
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // list：邻接表，用于存储课程之间的依赖关系。list.get(n2) 存储了所有依赖于 n2 的课程 n1
        List<List<Integer>> list = new ArrayList<>();
        // count：入度表，记录每门课程的前置课程数量。如果 count[i] == 0，说明课程 i 没有前置依赖
        int[] count = new int[numCourses];
        // deque：双端队列，用于执行 BFS，存放当前所有可以直接学习的课程（入度为 0）
        Deque<Integer> deque = new LinkedList<>();
        // result：记录已经成功学习完成的课程总数
        int result = 0;

        // 初始化邻接表：为每一门课程创建一个独立的列表
        for (int i = 0; i < numCourses; i++) {
            list.add(new ArrayList<>());
        }

        // 存储依赖关系以及前置课程的数量
        for (int[] item : prerequisites) {
            // n1：当前依赖关系中的目标课程（需要前置课程的课程）
            int n1 = item[0];
            // n2：当前依赖关系中的前置课程（必须先学的课程）
            int n2 = item[1];
            // 添加依赖关系：list.get(n2) 中加入 n1，表示 n1 依赖于 n2
            list.get(n2).add(n1);
            // 因为 n1 多了一门前置课程 n2，所以 n1 的入度 +1
            count[n1]++;
        }

        // 初始遍历：将所有没有任何前置课程（入度为 0）的课程加入队列
        for (int i = 0; i < count.length; i++) {
            if (count[i] == 0) {
                deque.offer(i);
            }
        }

        // BFS 循环：只要队列中有课可以学，就继续循环
        while (!deque.isEmpty()) {
            // 从队列中弹出一门当前可以学习的课程
            int data = deque.poll();
            // 学习完一门课，已完成课程数量 +1
            result++;
            
            // 遍历所有依赖于当前弹出的课程 data 的后继课程
            for (Integer integer : list.get(data)) {
                // 因为 data 已经学完，所以后继课程 integer 的前置课程数量减 1
                count[integer]--;
                // 如果 integer 的前置课程数量减到了 0，说明它也可以被学习了，加入队列
                if (count[integer] == 0) {
                    deque.offer(integer);
                }
            }
        }
        // 如果最终学习完成的课程数等于总课程数，说明没有循环依赖，返回 true
        return result == numCourses;
    }

    // ================= 思路 2：DFS（深度优先搜索检测环） =================
    public boolean canFinish1(int numCourses, int[][] prerequisites) {
        // 1. 建图（记录 a -> b 的依赖关系，即课程 a 依赖于前置课程 b）
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            graph.add(new ArrayList<>());
        }
        for (int[] preq : prerequisites) {
            int a = preq[0]; // 目标课程
            int b = preq[1]; // 前置课程
            graph.get(a).add(b); // 表示 a 依赖 b (边 a -> b)
        }

        // status：状态数组，用于记录每个节点的搜索状态。
        // 0：未访问； 1：正在搜索中（当前递归栈中）； 2：已搜索完成（无环）
        int[] status = new int[numCourses];

        // 遍历每一门课，如果它还没被访问过，则对其进行 DFS 环检测
        for (int i = 0; i < numCourses; i++) {
            if (status[i] == 0) {
                // 如果发现环，则直接返回 false
                if (hasCycle(i, graph, status)) {
                    return false;
                }
            }
        }
        // 全部遍历完都没有发现环，返回 true
        return true;
    }

    // hasCycle：DFS 环检测辅助函数
    boolean hasCycle(int course, List<List<Integer>> graph, int[] status) {
        // 标记当前课程正在探索中（状态设为 1）
        status[course] = 1;
        
        // 遍历当前课程依赖的所有前置课程
        for (Integer integer : graph.get(course)) {
            if (status[integer] == 0) {
                // 如果前置课程未访问，递归探查该前置课程
                if (hasCycle(integer, graph, status)) {
                    return true; // 如果深层递归发现环，向上传递 true
                }
            } else if (status[integer] == 1) {
                // 如果前置课程处于状态 1，说明当前路径中重复遇到了同一个节点，即发现了环
                return true;
            }
        }
        
        // 如果所有依赖的课程都检查完毕且没发现环，标记当前课程探索完成（状态设为 2）
        status[course] = 2;
        return false;
    }
    
}