AcWing 848. 有向图的拓扑序列
原题链接
简单
作者:
369pro
,
2024-03-25 15:57:41
,
所有人可见
,
阅读 3
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
const int N = 1e5+5;
// e[u] = v表示u->v的一条边
vector<int> e[N];
// indegree[i]表示节点i的入度
int indegree[N];
vector<int> top_sort(int n){
queue<int> q;
vector<int> res;
for(int i = 1; i <= n; i++){
if(indegree[i] == 0){
q.push(i);
}
}
while(!q.empty()){
int x = q.front();
q.pop();
res.push_back(x);
// 把所有以x为起点的边的终点入度减一
for(auto v : e[x]){
indegree[v]--;
if(indegree[v] == 0) q.push(v);
}
}
return res;
}
int main(){
int n, m;
cin >> n >> m;
while(m--){
int u, v;
cin >> u >> v;
e[u].push_back(v);
indegree[v]++;
}
vector<int> res = top_sort(n);
if(res.size() != n) cout << -1;
else{
for(int i = 0; i < res.size(); i++) cout << res[i] << " ";
}
}