如何判断有向无环图：构造有向无环图

拓扑序列：可以用来判断一个有向图是否有环！
拓扑排序可以判断有向图是否存在环。我们可以对任意有向图执行上述过程，在完成后检查A序列的长度。 若A序列的长度小于图中点的数量，则说明某些节点未被遍历，进而说明图中存在环。

拓扑排序是结合bfs框架来实现的，每次从入度为0的点开始搜索；所以需要先预处理出来所有入度为0的节点，入队，然后去遍历这些入度为0的点，每次将这些点进行逻辑上的删除，然后更新它的直接邻接点的入度，如果直接邻接点的入度减为0，则将其也入队！

1. 建立一个队列，负责按照拓扑序列存取节点。
2. 预处理所有点的入度d[i], 起初把所有入度为0的点入队。
3. 取出队头节点t, 把 t 加入拓扑序列 – 队列q的末尾。
4. 对于从x出发的每条边x->y，y即为x的直接邻接点， 把d[y]−−。若被减为0， 则把y入队。
5. 重复第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;
}```