当前位置：首页 > news >正文

44.Acwing基础课第848题-简单-有向图的拓扑序列

news 2026/5/28 1:55:10

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≤10⁵

输入样例：

输出样例：

1 2 3

绘图14

解题思路

首先记录各个点的入度
然后将入度为 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个顶点。
主函数
- main函数从标准输入读入顶点数n和边数m，初始化邻接表h[]，并循环读取每一条边，更新邻接表和顶点入度d[]。
- 调用topsort函数执行拓扑排序。如果排序成功，输出排好序的顶点序列；否则，输出-1表示该图不是DAG，不能进行拓扑排序。
关于d[j]--
- 对于d[j]--，这并不会导致入度为负数值。当我们从队列中取出顶点t时，t的入度肯定是0，因为只有入度为0的点才会被加入队列。然后，我们遍历t的所有出边。在这个过程中，我们减少每个后继者j的入度，这表示我们去掉了从t到j的一条边。所以，d[j]--实际上是一个计数的减少过程，由于边的移除而减少。所以，d[j]最多只会从1减到0，而不会减到负数。