概念

拓扑排序，就是将图中的所有节点展开成一维序列，对于序列中任意的节点 ，如果在序列中 在 的前面，则说明在图中存在从 出发到达 的通路，即 排在 的前面，反之亦然。

入度

有多少条边指向该节点。

出度

由该节点指向其出边的条数。
对于有向图的拓扑排序，我们可以使用 **BFS** 的方式输出拓扑排序：

1. 起始阶段：将所有入度为 0 的节点入队。
2. 从队列中进行节点出队操作，出队序列就是我们输出的拓扑排序。对于弹出的节点

，遍历 的所有出度，统称 ，对 的做入度减 1 操作，含义是因为 从队列中弹出，被添加到拓扑序中，等价于 从图中被移除。

1. 判断 的入度是否为 0，如果是则 入队，加入拓扑排序。

以上操作能完成的前提是：必然能够找到至少一个入度为 0 的起点。

问题转化

1. 在图论中，一个有向无环图必然存在至少一个拓扑序与之对应，反之亦然。
2. 有向无环图的拓扑序必然存在（至少）一个入度为 0 的点。

   模板

   
   

题目

• 851. 喧闹和富有
• 802. 找到最终的安全状态
• 207. 课程表

  题解

  851. 喧闹和富有

  
  拓扑排序：

1. 构建邻接矩阵/邻接表。
2. 计算入度数组。
3. 将入度为 0 的节点放入队列 queue。
4. while(!queue.isEmpty())。
5. 弹出节点 i，遍历 i 所有指向的其它节点，使其入度数减 1，如果入度数 = 0，则添加进队列中。

本题有点绕，求一个 ans[x] = y 数组，含义为比 x 钱多的所有人中，quiet 最小的为 y 。

1. 每个节点的默认安静值是自己。

2. 数组 ans 保存每个节点对应的最小安静值所对应的节点 ID，所以在 #1 比较的时候，也是使用 ans[pool] 来操作。

   class Solution {
    public int[] loudAndRich(int[][] richers, int[] quiet) {
        int len = quiet.length;
        // 在所有拥有钱肯定不少于person[x]的人中，person[y]是最安静的
        int[] ans = new int[len];
        // 入度数组
        int[] in = new int[len];
        // ① 建图（邻接表、邻接矩阵），并统计入度数
        // (a, b) a比b有钱，构建一个有向图，a->b
        List<Integer>[] table = buildGraph(richers, in, len);
        int k = 0;
        // 将入度 0 放入队列中
        Deque<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < len; i++) {
            ans[i] = i;
        }
        for (int i = 0; i < len; i++) {
            // 初始化 ans 数组
            // ans[i] = quiet[i];
            if (in[i] == 0) {
                queue.addLast(i);
            }
        }
        // 拓扑排序
        while (!queue.isEmpty()) {
            int richer = queue.pollLast();
            // 获取 removeIndex 指向的所有节点
            List<Integer> targetList = table[richer];
            for (int poor : targetList) { // i 表示所指向的节点
                in[poor]--; // 入度数减 1
                // #1
                if (quiet[ans[poor]] > quiet[ans[richer]]) {
                    ans[poor] = ans[richer];
                }
                if (in[poor] == 0) {
                    queue.addLast(poor);
                }
            }
        }
        return ans;
    }
    // 构建邻接矩阵图
    List<Integer>[] buildGraph(int[][] richers, int [] in, int len) {
        List<Integer>[] graph = new LinkedList[len];
        for (int i = 0; i < len; i++) {
            graph[i] = new LinkedList<>();
        }
        for (int[] richer : richers) {
            int from = richer[0];
            int to = richer[1];
            in[to]++;
            graph[from].add(to);
        }
        return graph;
    }
   }