题目描述
给定一个n个点m条边的有向图,点的编号是1到n,图中可能存在重边和自环。
请输出任意一个该有向图的拓扑序列,如果拓扑序列不存在,则输出-1。
C++ 代码
#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; i = ne[i])
if(--d[e[i]] == 0) q.push(e[i]); //如果 j 入度为0,加入队列当中
}
if(cnt < n) return 0;
return 1;
}
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 || top[1] == 0) cout << "-1";
else for(int i = 1; i <= n; ++ i ) cout << top[i] <<" ";
return 0;
}
代码过不了啊
cnt = 1这个为啥不是零
从0从1都可以~