拓扑序列
作者:
巷港
,
2022-03-27 11:39:20
,
所有人可见
,
阅读 189
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1e5 + 10;
int e[N], ne[N], h[N], top[N], d[N];
int idx, n, m, cnt = 1;
void 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 ) // 将所有入度为0的点加入队列
if(d[i] == 0) q.push(i);
while(q.size()){
int t = q.front(); // 每次取出队列的首部
top[cnt ++] = t; // 加入到拓扑序列中
q.pop();
for(int i = h[t]; i!=-1; i = ne[i])
{
int j=e[i];
d[j]--; //这个点的入度-1
if (d[j]==0) q.push(j); //如果入度为0了,就入队
}
}
if(cnt < n) return false; //说明此时有节点没有在队列中,即没有拓扑序列
return true;
}
int main(){
int a, b;
cin >> n >> m;
memset(h, -1, sizeof h);
while(m -- )
{
cin >> a >> b;
add(a, b);
d[b] ++;
}
if(topsort() == 0) cout << "-1";
else for(int i = 1; i <= n; ++ i ) cout << top[i] <<" ";
return 0;
}