一、基本代码和思路

1.代码

package com.Kahn;

import java.util.*;

public class TopologicalSort {
    public static void main(String[] args) {
        // 测试用例：可以学完
        int[][] pre1 = {{1,0}, {2,1}, {3,2}};
        System.out.println(canFinish(4, pre1));  // true

        // 测试用例：有环
        int[][] pre2 = {{1,0}, {0,1}};
        System.out.println(canFinish(2, pre2));  // false
    }

    public static boolean canFinish(int n, int[][] prerequisites) {
        // 1. 建图
        List<Integer>[] graph = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }
        int[] inDegree = new int[n];

        for (int[] pre : prerequisites) {
            int from = pre[1];  // 先修课
            int to = pre[0];    // 后续课
            graph[from].add(to);
            inDegree[to]++;
        }

        // 2. 队列初始化
        Queue<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }

        // 3. BFS
        int count = 0;
        while (!queue.isEmpty()) {
            int cur = queue.poll();
            count++;
            for (int neighbor : graph[cur]) {
                inDegree[neighbor]--;
                if (inDegree[neighbor] == 0) {
                    queue.offer(neighbor);
                }
            }
        }

        // 4. 判断
        return count == n;
    }
}

2.思路讲解

拓扑排序可以判断有向图是否有环

并查集可以判断无向图是否有环

先建图，度为0的节点直接入队列，处理队列中的节点，更新邻居节点的度，度 - -;且count++；

最后比较count（count是 总共进入队列中的节点个数）和 n的值，若count==n 说明是有向无环图，否则就是出现count<n的情况也就是有向有环图。（为什么count<n呢？ 因为成环的那几个节点你指我我指你，度不可能为0，就没办法入队列）。

二、刷题

207. 课程表

判断是否有环 return count==n;

210. 课程表 II

返回排序的其中一种序列

310. 最小高度树

（剥洋葱思路） 把叶子节点如队列往中间剥，再把满足条件的新的叶子节点存入队列，直到最后剩余的节点（剩余节点remain=总节点n-叶子节点queue.size() ）当remain<=2时，最后队列剩余的节点就是答案

444. 序列重建 

关键在于多重检查的代码的思路。

1.保证节点是在1 - n之间的。

2.queue.size()>1则return false

3.最后的拓扑序列要与org的每个位置一一对应

851. 喧闹和富有

建图：rich->poor，rich的安静值小于poor的就更新poor的ans

if(quiet[ans[r]]<quiet[ans[p]]){
    ans[p]=ans[r];
}

802. 找到最终的安全状态

跟851一样都是反向图

1203. 项目管理

三、拓扑排序的两种经典模型

模型 1：有向无环图 + 入度（最常见）

适用：从依赖少的往依赖多的推进

步骤：

1. 建图

2. 计算入度

3. 入度为 0 的入队

4. BFS，每次出队时减少邻居入度

5. 入度变 0 的再入队

对应题目：207、210、2050、310（无向图变体）

// 模板
while (!queue.isEmpty()) {
    int u = queue.poll();
    for (int v : graph[u]) {
        if (--inDegree[v] == 0) {
            queue.offer(v);
        }
    }
}

---

模型 2：反向图 + 出度（你刚做的 802）

适用：从「终点」往回推，找哪些点最终能走到终点

关键判断：

• 原问题问的是「哪些节点是安全的/满足条件的」

• 而条件是从这个节点出发，所有路径都到终点

步骤：

1. 建反向图

2. 计算原图的出度

3. 出度为 0 的入队（终点）

4. BFS 反向图，减少前驱的出度

5. 出度变 0 的前驱也安全

对应题目：802、851（富人影响穷人，本质也是反向传播）