题目描述
终于顶不住使用数组模拟队列了,开始使用stl实现算法了
C++ 代码
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
#include <vector>
using namespace std;
const int N = 100010;
int n,m;
int e[N],ne[N],h[N],d[N];
int idx;
int msize;
vector<int> result;
int add(int a,int b){
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
bool topsort(){
queue<int> q;
for(int i = 1;i <=n;++i){
if(!d[i]){
msize++;
q.push(i);
result.push_back(i);
}
}
while(!q.empty()){
int t = q.front();
q.pop();
for(int i = h[t]; i != -1;i = ne[i]){
int j = e[i];
d[j]--;
if(d[j] == 0){
q.push(j);
result.push_back(j);
msize++;
}
}
}
if(msize == n){
return true;
}else{
return false;
}
}
int main(){
cin >> n >> m;
memset(h,-1,sizeof h);
while(m--){
int a,b;
cin >> a >> b;
add(a,b);
//b节点的入度+1
d[b]++;
}
if(topsort()){
for(int i = 0;i < result.size();++i){
cout << result[i] <<" ";
}
}else{
cout << "-1" <<endl;
}
return 0;
}