【ACWing】848. 有向图的拓扑序列

#【ACWing】848. 有向图的拓扑序列| 来源: 网络整理| 查看: 265

题目地址：

https://www.acwing.com/problem/content/850/

给定一个 n n n个点 m m m条边的有向图，点的编号是 1 1 1到 n n n，图中可能存在重边和自环。输出其任意一个拓扑序列。如果不存在则返回 − 1 -1 −1。

输入格式：第一行包含两个整数 n n n和 m m m。接下来 m m m行，每行包含两个整数 x x x和 y y y，表示存在一条从点 x x x到点 y y y的有向边 ( x , y ) (x, y) (x,y)。

输出格式：共一行，如果存在拓扑序列，则输出任意一个合法的拓扑序列即可。

数据范围： 1 ≤ n , m ≤ 1 0 5 1\le n,m\le 10^5 1≤n,m≤105

可以用BFS来做。开个队列，先将所有入度为 0 0 0的点入队，每次出队一个数，就将其加入答案，并将其所有的出边删掉（即将其邻接点入度减 1 1 1），当其某个邻接点入度为 0 0 0的时候将这个点入队。最后如果答案里的点数小于 n n n说明不存在拓扑序，输出 − 1 -1 −1，否则输出答案。代码如下：

#include #include #include using namespace std; const int N = 100010; int n, m; int h[N], e[N], ne[N], idx; int d[N]; bool vis[N]; int res[N], cnt; void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx++; } bool bfs() { queue q; for (int i = 1; i int j = e[i]; d[j]--; if (!d[j]) q.push(j); } } return cnt == n; } int main() { memset(h, -1, sizeof h); cin >> n >> m; while (m--) { int a, b; cin >> a >> b; add(a, b); d[b]++; } if (!bfs()) puts("-1"); else for (int i = 1; i vis[u] = 0; for (int i = h[u]; i != -1; i = ne[i]) { int j = e[i]; if (vis[j] == -1 && !dfs(j)) return false; else if (!vis[j]) return false; } vis[u] = 1; res[++cnt] = u; return true; } int main() { memset(h, -1, sizeof h); cin >> n >> m; while (m--) { int a, b; cin >> a >> b; add(a, b); } memset(vis, -1, sizeof vis); for (int i = 1; i

【本文地址】

公司简介

联系我们