浙江
做番茄炒蛋这事，其实藏着个经典的算法问题。你得先洗番茄才能切番茄，先打蛋才能搅拌蛋液，切番茄和搅拌蛋液可以同时干，但都备好了才能下锅。这一串"谁必须在谁前面"的约束，就是拓扑排序要解决的活儿。
说白了，拓扑排序干的事很简单：给一个有向无环图（DAG）的所有顶点排个序，规则就一条——如果 A 指向 B，那 A 必须排在 B 前面。
注意，前提是"无环"。如果 A 依赖 B、B 又依赖 A，那就成了死循环，谁也排不了。这也是为什么拓扑排序只能用在 DAG 上——有环的图根本排不出一个合理的顺序来。
那具体怎么排？最经典的思路叫 Kahn 算法，也叫入度法。入度，就是有多少个节点指向它。比如节点 1 被两个节点指着，入度就是 2；节点 2 没人指，入度就是 0。
整个流程就三步：
第一步，把图中所有入度为 0 的节点找出来，塞进一个队列。入度为 0 意味着没有前置依赖，随时可以开工。
第二步，从队列里取出一个节点，输出它，然后把它指向的所有节点的入度减 1。相当于这个活干完了，它罩着的那些兄弟少了一个依赖。
第三步，重复第二步，过程中一旦有节点入度变成 0，就把它加进队列。直到队列空了，输出的顺序就是答案。
这算法时间复杂度 O(V+E)，每个节点每条边都过一遍，效率很高，代码也不难写：
#include
usingnamespacestd;
vector e[105];// e[i] 存 i 指向的所有节点
queue q; // 存放入度为 0 的节点
intd[105], vis[105];
intmain(){
intn; cin >> n;
for(inti =1; i <= n; i++) {
while(1) {
inta; cin >> a;
e[i].push_back(a);
if(a ==0)break;
d[a]++;// 记录入度
}
}
for(inti =1; i <= n; i++) {
if(d[i] ==0) { q.push(i); vis[i] =1; }
}
while(!q.empty()) {
intx = q.front(); q.pop();
cout << x <<" ";
for(inti : e[x]) {
if(vis[i])continue;
d[i]--;
if(d[i] ==0) { vis[i] =1; q.push(i); }
}
}
return0;
}
写代码的时候有几个坑要注意：一是要标记已访问，防止同一个节点重复入队；二是入度减完之后要立刻判断是不是 0，是 0 才入队，不然队列里会混进还没准备好的节点。
光讲概念没意思，来看道真题。洛谷 P4017 最大食物链计数，给你一个食物网，数出最大食物链的数量。生物意义上，最左端是不会捕食其他生物的生产者，最右端是不会被捕食的消费者。
这题就是拓扑排序加 DP：dp[i] 表示到达节点 i 的路径数。把所有入度为 0 的生产者初始化为 1，然后按拓扑序往下推，每经过一条边就把路径数累加过去，最后把出度为 0 的消费者节点的 dp 值加起来，就是答案。
讲道理，拓扑排序在真实项目里到处都是：编译器做依赖分析、构建工具排任务的执行顺序、课程表排先修课、包管理器解决依赖关系……你天天在用，只是没意识到它叫这个名字。
我个人觉得，这种"基础算法"反而是最值得花时间吃透的，因为它是很多工程问题的底层骨架。你在项目里用过拓扑排序吗？评论区聊聊你的场景。
特别声明：以上内容(如有图片或视频亦包括在内)为自媒体平台“网易号”用户上传并发布，本平台仅提供信息存储服务。
Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.
