AcWing 848. 有向图的拓扑序列
原题链接
简单
作者:
满目星河_0
,
2021-03-31 12:34:23
,
所有人可见
,
阅读 340
带注释(超详细)
//算法思想:将入读为0的点加入队列,遍历其下一个点并把前一个点删除(这时候下一个点的
//入度如果是0就将他加入队列),这样就能保证加入队列的点的顺序就是拓扑排序后的顺序。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
const int N=1e5+10,M=2*N;
int h[N],e[M],ne[M],idx;
int n;
int q[N];
int d[N];//用来记录各个点入度
void add(int a,int b){//插入模板
e[idx]=b;
ne[idx]=h[a];
h[a]=idx++;
}
bool topusort(){
int hh=0,tt=-1;
//如果是tt先加,则tt=-1
for(int i=1;i<=n;i++){//将入度为0的点加入队列
if(d[i]==0)
q[++tt]=i;
}
while(hh<=tt){
int t=q[hh++];//t表示对头
//h[t]表示以序号t为开头的链表。
for(int i=h[t];i!=-1;i=ne[i]){//i指的是某个节点,并不是值
int j=e[i];//一定是当前节点的值
d[j]--;//将前面那条边删掉
if(d[j]==0) q[++tt]=j; //如果入度为0,则加入队列
}
}
return (n-1==tt); //如果存在拓扑结构tt==n-1
}
int main(){
int m;
cin>>n>>m;
memset(h,-1,sizeof(h));//初始化链表头
int a,b;
for(int i=0;i<m;i++){
cin>>a>>b;
add(a,b);
d[b]++;//对应点的入度加1
}
if(topusort()){//加入队列的顺序刚好就是拓朴序列
for(int i=0;i<n;i++) cout<<q[i]<<" ";
}
else cout<<"-1";
return 0;
}