有向无环图是拓扑排序
拓扑排序将图中所有的顶点排成一个线性序列，使得所有的有向边均从序列的前面指向后面。
拓扑排序使用深度优先搜索来实现，图中有环则无法进行拓扑排序
一个有向图，如果图中有入度为0的点，就把这个点删掉，同时也删掉这个点所连的边
一直进行上面的处理过程，如果发现所有的点都能被删掉，则这个图可以进行拓扑排序
算法思路:首先记录各个点的入度
然后将入度为0的点放入队列，将队列里的点依次出对，然后删除这个点出发的边，删掉这个边同时边的另一侧的入度-1
如果所有的点都进过队列，则可以进行拓扑排序，否则输出-1，代表不能进行拓扑排序
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int N = 100010;
vector<int> g[N]; // 邻接表存储图
int in_degree[N]; // 记录每个点的入度
int n, m; // n 个点，m 条边
bool topological_sort() {
queue<int> q;
for (int i = 1; i <= n; i++) {
if (in_degree[i] == 0) {
q.push(i); // 将所有入度为 0 的点加入队列
}
}
while (!q.empty()) {
int u = q.front();
q.pop();
cout << u << " "; // 输出拓扑排序的顺序
for (auto v : g[u]) {
in_degree[v]--; // 删除边 (u, v)
if (in_degree[v] == 0) {
q.push(v); // 如果节点 v 的入度变为 0，则加入队列
}
}
}
// 如果所有点都被访问过，说明是有向无环图，返回 true
for (int i = 1; i <= n; i++) {
if (in_degree[i] != 0) {
return false;
}
}
return true;
}
int main() {
cin >> n >> m; // 输入点的个数和边的个数
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
g[a].push_back(b); // 添加边 (a, b)
in_degree[b]++; // b 的入度加 1
}
if (topological_sort()) {
cout << "拓扑排序结果：";
} else {
cout << "图中存在环！";
}
return 0;
}
