AcWing 1639. 拓扑顺序
原题链接
简单
作者:
Abide_HAO
,
2024-02-15 22:07:10
,
所有人可见
,
阅读 62
拓扑序列
#include<iostream>
#include<cstring>
using namespace std;
const int N=1010,M=10010;
int h[N],e[M],ne[M],idx=1;
int degree[N],d[N];//前者存储入度,后者用来copy前者
int ask[N];//存储待检测的序列
int n,m,k;
void add(int x,int y){//加一条a->b的边
e[idx]=y,ne[idx]=h[x],h[x]=idx++;
}
bool topsort(){//判断是否是拓扑序列
memcpy(d,degree,sizeof degree);
for(int i=0;i<n;i++){
if(d[ask[i]])return false;
for(int j=h[ask[i]];j!=-1;j=ne[j])
d[e[j]]--;
}
return true;
}
int main(){
cin>>n>>m;
memset(h,-1,sizeof h);
for(int i=1;i<=m;i++){
int a,b;
scanf("%d%d",&a,&b);
degree[b]++;//b的入度加一
add(a,b);
}
cin>>k;
for(int i=0;i<k;i++){
for(int j=0;j<n;j++)cin>>ask[j];
if(!topsort())cout<<i<<" ";
}
return 0;
}