LeetCode 207. 课程表

207. 课程表

解题思路

前置知识:拓扑排序

逐步删除入度为0的节点，直到没有入度为0的节点为止

• 如果所有节点都被删除了，说明图中没有环，课程表是可以完成的，返回 true；
• 如果还有节点没有被删除，说明图中存在环，课程表无法完成，返回 false。

参考代码

DFS 三色标记法

class Solution {

    // 是否有环
    private boolean res = false;

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<Integer>[] g = new ArrayList[numCourses];
        Arrays.setAll(g, i -> new ArrayList<>());
        for (int[] p : prerequisites) {
            g[p[1]].add(p[0]);
        }

        /**
            0: 当前节点没有被访问
            1: 当前节点正在被访问
            2: 当前节点访问结束
         */
        int[] state = new int[numCourses];

        for (int i = 0; i < numCourses; i ++) {
            if(state[i] == 0) {
                dfs(i, g, state);
            }
        }

        return !res;
    }

    private void dfs(int x, List<Integer>[] g, int[] state) {
        // 访问结束直接返回
        if(state[x] == 2) {
            return;
        }
        // 再次访问 x 节点，有环
        if(state[x] == 1) {
            res = true;
            return;
        }
        // 正常访问 x 节点
        state[x] = 1;
        for(int gg : g[x]) {
            dfs(gg, g, state);
        }
        // 访问结束
        state[x] = 2;
    }
}

邻接矩阵

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int res = numCourses;
        int[] indegress = new int[numCourses];
        int[][] courses = new int[numCourses][numCourses];
        Queue<Integer> queue = new LinkedList<>();
        for (int[] p : prerequisites) {
            courses[p[0]][p[1]] = 1;
            indegress[p[1]]++;
        }

        for (int i = 0; i < indegress.length; i++) {
            if (indegress[i] == 0) {
                queue.add(i);
            }
        }

        while (!queue.isEmpty()) {
            int course = queue.remove();
            res--;
            for (int i = 0; i < numCourses; i++) {
                if (courses[course][i] == 1) {
                    indegress[i]--;
                    if (indegress[i] == 0) {
                        queue.add(i);
                    }
                }

            }
        }
        return res == 0;
    }
}