题目分析
考察 拓扑图有关入度 的性质
C++ 代码
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=10010;
int h[N],e[N],ne[N],idx;
int d[N]; // 入度
int backup[N]; // 入度
int a[N];
int n,m,k;
void Init(){
memset (h,-1,sizeof h);
}
void add(int a,int b){
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
bool judge(){
for(int j=1;j<=n;j++){
int id=a[j];
if(backup[id]!=0) return false;
for(int i=h[id];i!=-1;i=ne[i]){
int u=e[i];
backup[u]--;
}
}
return true;
}
int main(){
Init();
scanf("%d%d",&n,&m);
while(m--){
int a,b;
cin>>a>>b;
add(a,b);
d[b]++;
}
cin>>k;
for(int i=0;i<k;i++){
memcpy(backup,d,sizeof d);
for(int i=1;i<=n;i++) cin>>a[i];
if(!judge()) printf("%d ",i);
}
return 0;
}