拓扑排序是什么
拓扑排序是一种用于有向无环图（DAG）的排序算法，它将图中的顶点线性排列，使得对于每一条边u→v，顶点 u 在顶点 v 之前。
拓扑排序提供了一种方式来安排任务的顺序，确保每个任务在其依赖的任务之前完成。
拓扑排序算法步骤
1.有向无环图（DAG）
拓扑排序只适用于有向无环图。如果图中存在环，则无法确定一个有效的拓扑排序，因为某些任务会相互依赖，导致循环依赖
2.入度
在图中，每个节点都有一个入度（指向该节点的数量）和出度（从该节点指向其他节点的边的数量）。
拓扑排序的一个常用方法是利用节点的入度来决定处理顺序
3.具体算法设计
- 计算每个节点的入度
- 选择入度为0的节点，从图中选择入度为0的节点（即没有依赖的任务），并将他们添加到一个列表或队列中
- 处理节点，从列表中取出一个节点，输出它，并减少与其相连的所有节点的入度，如果某个相连节点的入度变为0，则将其加入到列表中
- 重复上述步骤，直到所有节点都被处理，如果在处理过程中列表为空但仍有未处理的节点，则说明图中存在环，无法进行拓扑排序
- 最终得到的输出顺序即为拓扑排序的结果。由于处理顺序是基于节点的入度，因此确保了每个节点在其依赖的节点之后
4.实现方法
-
深度优先搜索（DFS）
通过DFS遍历图，在回溯时将节点压入栈中，完成DFS后，栈中的节点顺序即为拓扑排序
-
Kahn算法（基于入度的方法）
维护一个入度数组，使用队列来处理入度为 0 的节点。每次处理一个节点后，更新相连节点的入度，并将新的入度为 0 的节点加入队列。
代码
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
using namespace std;
int main() {
int m, n, s, t;
cin >> n >> m;
vector<int> inDegree(n, 0); // 记录每个文件的入度
unordered_map<int, vector<int>> umap;// 记录文件依赖关系
vector<int> result; // 记录结果
while (m--) {
// s->t，先有s才能有t
cin >> s >> t;
inDegree[t]++; // t的入度加一
umap[s].push_back(t); // 记录s指向哪些文件
}
queue<int> que;
for (int i = 0; i < n; i++) {
// 入度为0的文件，可以作为开头，先加入队列
if (inDegree[i] == 0) que.push(i);
//cout << inDegree[i] << endl;
}
// int count = 0;
while (que.size()) {
int cur = que.front(); // 当前选中的文件
que.pop();
//count++;
result.push_back(cur);
vector<int> files = umap[cur]; //获取该文件指向的文件
if (files.size()) { // cur有后续文件
for (int i = 0; i < files.size(); i++) {
inDegree[files[i]] --; // cur的指向的文件入度-1
if(inDegree[files[i]] == 0) que.push(files[i]);
}
}
}
if (result.size() == n) {
for (int i = 0; i < n - 1; i++) cout << result[i] << " ";
cout << result[n - 1];
} else cout << -1 << endl;
}