如何求有向图的拓扑序列？

44.Acwing基础课第848题-简单-有向图的拓扑序列 题目描述 给定一个 n个点 m条边的有向图，点的编号是 1到 n，图中可能存在重边和自环。 请输出任意一个该有向图的拓扑序列，如果拓扑序列不存在，则输出 −1。 若一个由图中所有点构成的序列 A满足：对于图中的每条边 (x,y)，x在 A中都出现在 y之前，则称 A是该图的一个拓扑序列。 输入格式 第一行包含两个整数 n和 m。 接下来 m行，每行包含两个整数 x 和 y，表示存在一条从点 x到点 y的有向边 (x,y)。 输出格式 共一行，如果存在拓扑序列，则输出任意一个合法的拓扑序列即可。 数据范围 1≤n,m≤105 输入样例： 3 3 1 2 2 3 1 3 输出样例： 1 2 3 解题思路 首先记录各个点的入度 然后将入度为 0 的点放入队列 将队列里的点依次出队列，然后找出所有出队列这个点发出的边，删除边，同时边的另一侧的点的入度 -1。 如果所有点都进过队列，则可以拓扑排序，输出所有顶点。否则输出-1，代表不可以进行拓扑排序。 代码： #include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 100010; int n,m; int h[N],e[N],ne[N],idx; int q[N],d[N];//q[]表示队列，d表示入度 //构建节点a到b的边 void add(int a, int b) { e[idx] = b; ne[idx] = h[a]; h[a] = idx; idx++; } bool topsort() { int hh = 0, tt = -1; for(int i = 1; i <= n; i++)//所有入度为0的点入队 if(!d[i]) q[++tt] = i; while(hh<=tt)//队列非空 { int t = q[hh++]; for(int i = h[t]; i != -1; i = ne[i]) { int j = e[i]; d[j]--; if(d[j] == 0) q[++tt] = j; } } return tt == n-1; } int main() { cin >> n >> m; memset(h, -1, sizeof h); for(int i = 1; i <= m; i++) { int x, y; cin >> x >> y; add(x,y); d[y]++; } if(topsort()) { for(int i = 0; i < n; i++) printf("%d ",q[i]); puts(""); } else puts("-1"); return 0; } 这段代码的核心功能是，通过拓扑排序算法来确定一个有向图中的顶点顺序，这个顺序满足：对于图中的每一对顶点u和v，如果存在从u到v的路径，则在排序结果中u出现在v之前。这是有向无环图（DAG）的一种特性。 邻接表的构建 add函数用于在邻接表中添加一条从顶点a到顶点b的边。它的工作原理是将新边插入到以a为头的链表的起始位置。 h[a]记录首个离开a的边的索引，e[idx]是该边到达的顶点，ne[idx]记录该边的下一条边的索引。idx是全局计数器，用于分配新边的索引。 拓扑排序算法 topsort函数实现拓扑排序。它使用队列q[N]来记录排序结果。 先将所有入度为0的顶点添加到队列中，这些顶点没有任何入边，并且它们将是拓扑排序的起始顶点。 然后，算法进入循环，每次从队列中取出一个顶点t，并检查每一个t的后继者j。每处理一个后继者，就将该顶点的入度d[j]减1，因为我们已经“考虑”了从 t到j的边。 如果后继者j的入度经过减少后变为0，则它也没有未处理的入边了，可以放入队列，等待后续处理。 排序成功的标志是所有顶点都被处理过一次，即队列包含了所有n个顶点。