AcWing 848. 有向图的拓扑序列
原题链接
简单
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int h[N],v[N],ne[N],idx;
int q[N],hh,tt=-1;//模拟队列
int indegree[N];//记录每个结点的入度
int n,m;
void add(int a,int b)
{
v[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
bool Topsort()
{
for(int i=1;i<=n;i++)//1~n编号的n个结点
if(indegree[i]==0)//入度为0的结点入队
q[++tt]=i;
while(hh<=tt)
{
int cur=q[hh++];
for(int i=h[cur];i!=-1;i=ne[i])
{
//所有以cur为起始点的边的终点的入度--
indegree[v[i]]--;
if(indegree[v[i]]==0)//如果入度减1后为0 则入队
q[++tt]=v[i];
}
}
return tt==n-1;
}
int main()
{
scanf("%d%d",&n,&m);
//初始化h[N]的所有元素为-1
memset(h,-1,sizeof(h));
for(int i=0;i<m;i++)
{
int x,y;scanf("%d%d",&x,&y);//x -> y的有向边
add(x,y);
//所以y的入度++
indegree[y]++;
}
if(Topsort())//如果存在拓扑序列 则进行输出
{
//使用模拟队列的好处 此时q[N]中存放的就是拓扑序列
for(int i=0;i<n;i++)
printf("%d ",q[i]);
puts("");
}
else puts("-1");
return 0;
}