AcWing 848. 有向图的拓扑序列
原题链接
简单
作者:
VictorWu
,
2020-02-23 16:08:06
,
所有人可见
,
阅读 703
拓扑排序
算法思想:bfs
- 把所有入度为0的点全部放入队列。
- 只要有入度为0的节点(队列不为空)则把该点输出,并把以该点t为入度的所有节点的入度减一。
- 把每个入度被减成0的节点放入队列
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, m;
vector<vector<int>> graph(N);
vector<int> inD(N);
vector<int> ans;
/*
n 节点个数,下标从1开始
graph 邻接表
inD 每个节点的入度
ans 保存拓扑序
*/
bool topsort() {
queue<int> q;
for (int i = 1; i <= n; i++) // 把所有入度为0的点全部加进队列
if (inD[i] == 0)
q.push(i);
while (!q.empty()) {
int t = q.front(); q.pop(); // 拿一个入度为0的点
ans.push_back(t);
for (int v : graph[t]) // 把以该点t为入度的点的入度减一
if (--inD[v] == 0)
q.push(v); // 若减成0,则入队
}
return ans.size() == n; // 若全部节点都被访问才说明有 拓扑序
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 0; i < m; i++) {
int a, b; scanf("%d%d", &a, &b);
graph[a].push_back(b);
++inD[b];
}
if (topsort()) for (int i = 0; i < ans.size(); i++) printf("%d ", ans[i]);
else puts("-1");
return 0;
}