拓扑排序
title: 拓扑排序
categories:
- ICPC
tags:
- null
abbrlink: fb40efc5
date: 2023-11-16 00:00:00
const int N = 100010;
int n,m,a,b;
vector<int> e[N], tp;
int din[N];//入度数组
bool toposort(){
queue<int> q;
for(int i = 1; i <= n; i++)
if(din[i]==0) q.push(i);
while(q.size()){
int x=q.front(); q.pop();
tp.push_back(x);
for(auto y : e[x]){
if(--din[y]==0) q.push(y);
}
}
return tp.size() == n;
}
int main(){
cin >> n >> m;
for(int i=0; i<m; i++){
cin >> a >> b;
e[a].push_back(b);
din[b]++;
}
if(!toposort()) puts("-1");
else for(auto x:tp)printf("%d ",x);
return 0;
}
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 爱飞鱼的blog!