织梦移动端网站建设阿里指数查询官网
拓扑序列：可以用来判断一个有向图是否有环！
拓扑排序可以判断有向图是否存在环。我们可以对任意有向图执行上述过程，在完成后检查A序列的长度。 若A序列的长度小于图中点的数量，则说明某些节点未被遍历，进而说明图中存在环。
拓扑排序是结合bfs框架来实现的，每次从入度为0的点开始搜索；所以需要先预处理出来所有入度为0的节点，入队，然后去遍历这些入度为0的点，每次将这些点进行逻辑上的删除，然后更新它的直接邻接点的入度，如果直接邻接点的入度减为0，则将其也入队！
- 建立一个队列，负责按照拓扑序列存取节点。
- 预处理所有点的入度d[i], 起初把所有入度为0的点入队。
- 取出队头节点t, 把 t 加入拓扑序列 – 队列q的末尾。
- 对于从x出发的每条边x->y，y即为x的直接邻接点， 把d[y]−−。若被减为0， 则把y入队。
- 重复第3∼4步直到队列为空， 此时队列q即为所求。
本题中心思想： 用 已确定方向的边 建好图后，给 未确定方向的边 设置方向 这部操作其实就是 加边 行为。如果当前图中已经存在 环
了，那么加额外的边是不能去掉这个 环 的（除非删掉环上的某一条边） 大致就是以上意思
由于我们只建立了有向边，而无向边的话是没有建立的，所以意味着建立的有向图不会经过所有的顶点，，那为什么生成的拓扑序列 就能够确保经过所有的顶点呢？
因为属于不同连通块亦能构成拓扑序，拓扑排序本身不会被局限在一个连通块内
对于无向边的节点，我们需要知道它在拓扑序列中的位置，而拓扑序列我们已经预处理出来了，只需要求出拓扑序列里，含无向边的两个点，让它们按照拓扑序列从前往后指向，就必然不会破坏拓扑序列并且合法！
代码：
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>using namespace std;const int N = 2e5 + 10, M = N;
int T, n, m;
int top[N], pos[N]; //存放拓扑序！
int h[N], e[M], ne[M], d[N], idx;
struct Edge{int a, b;
}edge[M];void add (int a, int b)
{e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}bool topsort ()
{queue<int> q; //定义一个队列！//预处理出来所有入度为0的节点：for (int i=1; i <= n; i ++)if (!d[i])q.push(i);int cnt = 0;while (q.size()){auto t = q.front();q.pop();top[cnt ++] = t; //存放拓扑序列！ for (int i=h[t]; ~i; i = ne[i]){int j = e[i];d[j] --;if (d[j] == 0)q.push(j);}}//判断存放的元素个数：if (cnt < n) return false;else return true;
}int main()
{cin >> T;while (T --){int cnt = 0;//初始化：memset (h, -1, sizeof (h));memset (d, 0, sizeof (d)); //度数数组！idx = 0;scanf ("%d%d", &n, &m);while (m --){int t, x, y;scanf("%d%d%d", &t, &x, &y);if (!t) edge[cnt ++] = {x, y};else{ //即为有向边！add (x, y);d[y] ++;}}if (!topsort()) //利用拓扑序列判断是否有环puts("NO");else{puts("YES");for (int i=1; i <= n; i ++) //输出拓扑序列：for (int j=h[i]; ~j; j = ne[j])printf ("%d %d\n", i, e[j]); //指代有向边！//记录每个点的位置：//pos[i]：表示的是i号节点在拓扑序列中的位置for (int i=0; i < n; i ++) pos[top[i]] = i;for (int i=0; i < cnt; i ++){int a = edge[i].a, b = edge[i].b;if (pos[a] > pos[b]) swap(a, b);printf ("%d %d\n", a, b);}}}return 0;
}```