课程表II

题目

版本1 正确

    // 有向图, 存储不同标号的节点, 所能到达的所有节点, 即所有有向边
    Map<Integer, List<Integer>> edgesMap = new HashMap<>();

    // 标记每个节点的状态：0=未搜索，1=搜索中，2=已完成
    int[] visited;

    // 判断有向图中是否有环
    boolean loop = Boolean.FALSE;

    // 存储结果
    int [] ans;

    // 往ans存储结果的时候, 是从后往前存的, 在拓扑排序中, 终点是在起点的后面的, 因此先添加的一定是最后一个元素
    int index;

    public int[] findOrder(int numCourses, int[][] prerequisites) {
        // 典型的拓扑排序问题, 即一个包含n个节点的有向图G, 我们给出它的节点编号的一种排列，如果满足：
        // 对于图 G中的任意一条有向边 (u, v)，u 在排列中都出现在 v 的前面。
        // 那么称该排列是图 G 的「拓扑排序」
        // 有向边(u, v)就代表节点u指向节点v, 即u作为v的前置条件.
        // 如果图中出现了环, 那么肯定无法求出拓扑排序

        // 什么说本题目是是一个拓扑排序问题呢?
        // 原因就是题目的本质就是给出一个所有课程的排列, 然后满足每门课程x的前置课程y在排列中都满足y排列在x前面
        // 就跟拓扑排序对于有向边节点的要求一摸一样
        // 因此每门课程可以视为有向图中的一个节点, 然后如果学习A课程必须先学习B课程, 那么在有向图中就构成了一条有向边
        // 由B指向A.

        // 首先构建一个有向图
        // 课程的标号就是从0到numCourses - 1
        // 记录每个课程作为起点, 都能到达哪些终点, 即每个课程作为起点的有向边都有哪些
        for (int i = 0; i < prerequisites.length; i ++) {
            // 要完成order[0], 必须先完成order[1], 即order[1]指向order[0]
            int [] order = prerequisites[i];
            List<Integer> temp = edgesMap.getOrDefault(order[1], new ArrayList<>());

            if (!temp.contains(order[0])) {
                temp.add(order[0]);
                edgesMap.put(order[1], temp);
            }

        }

        // 需要对有向图进行遍历, 寻找拓扑排序
        // 对于有向图中, 没有搜索过的节点作为起点, 进行DFS
        visited = new int[numCourses];
        ans = new int[numCourses];
        index = numCourses - 1;
        for (int i = 0; i < numCourses; i ++) {
            if (visited[i] == 0) {
                dfs(i);
            }
            // 如果出现了环, 那么肯定没有拓扑排序
            if (loop) {
                return new int[0];
            }
        }

        return ans;
    }


    public void dfs(int u) {
        // 一次dfs, 遇见的所有未搜索的节点编号都应该标记成搜索中, 这样遇见相同的编号, 就可以判断是否有环
        // 当该编号的节点寻找完所有的有向图后, 就变成了已完成
        visited[u] = 1;

        // 搜索其相邻节点
        // 注意不是所有课程都会作为前置课程的, 因此edgesMap,get(u)可能为null
        for (int v: edgesMap.getOrDefault(u, new ArrayList<>())) {
            // 如果「未搜索」那么搜索相邻节点
            if (visited[v] == 0) {
                dfs(v);
                if (loop) {
                    return;
                }
            }
            // 如果「搜索中」说明找到了环
            else if (visited[v] == 1) {
                loop = Boolean.TRUE;
                return;
            }
        }
        // 寻找完一个节点作为起点的所有有向边之后
        // 将节点标记为「已完成」
        visited[u] = 2;
        // 将节点添加到结果中
        ans[index] = u;
        index --;
    }
复制代码