有向图的拓扑序列
题目：
给定一个n个点m条边的有向图，图中可能存在重边和自环。
请输出任意一个该有向图的拓扑序列，如果拓扑序列不存在，则输出-1。
若一个由图中所有点构成的序列A满足：对于图中的每条边(x, y)，x在A中都出现在y之前，则称A是该图的一个拓扑序列。
输入格式
第一行包含两个整数n和m
接下来m行，每行包含两个整数x和y，表示存在一条从点x到点y的有向边(x, y)。
输出格式
共一行，如果存在拓扑序列，则输出拓扑序列。
否则输出-1。
数据范围
1≤n,m≤105
输入样例：
3 3
1 2
2 3
1 3
输出样例：
1 2 3
#include<iostream>
#include<algorithm>
#include<string.h>
#include<queue>
using namespace std;
const int N=100010;
int n,m;
int d[N];
int h[N],e[N],idx,ne[N];
int q[N];
bool st[N];
void add(int a,int b)
{
e[idx]=b;
ne[idx]=h[a];
h[a]=idx++;
}
int main()
{
int tt=-1,hh=0;
memset(h,-1,sizeof(h));
cin>>n>>m;
while(m--)
{
int a,b;
cin>>a>>b;
add(a,b);
d[b]++;
}
for(int i=1;i<=n;i++)
{
if(d[i]==0)
{
q[++tt]=i;
st[i]=1;}
}
while(tt>=hh)
{
int t=q[hh++];
for(int i=h[t];i!=-1;i=ne[i])
{
int j=e[i];
// printf("%d,d[%d]=%d\n",j,j,d[j]);
d[j]--;
if(d[j]==0) {
if(!st[j])
{
st[j]=1;
q[++tt]=j;
}
}
}
}
if(tt==n-1) for(int i=0;i<n;i++) printf("%d ",q[i]);
else printf("-1");
return 0 ;
}
查看5道真题和解析