大家好，又见面了，我是你们的朋友全栈君。
题意:在给定有向图中，对于给定查询序列是否是有向图中的一个拓扑序列，记录非法序列下标
tip：模拟拓扑排序
#include<iostream>
#include<vector>
using namespace std;
int in_num[1003]= {0};
int temp[1003]= {0};
vector<int> s[1003];
int checked(int x) {
if(temp[x])
return 1;
for(int i=0; i<s[x].size(); ++i)
temp[s[x][i]]--;//去边
return 0;
}
int main() {
int n,m;
cin>>n>>m;
for(int i=0; i<m; ++i) {
int a,b;
cin>>a>>b;
in_num[b]++;//记录b点入度
s[a].push_back(b);//记录a的出边
}
int k;
cin>>k;
vector<int>ans;
for(int i=0; i<k; ++i) {
int flag=0;
for(int l=1; l<=n; ++l)
temp[l]=in_num[l];
for(int j=0; j<n; ++j) {
int a;
cin>>a;
if(checked(a))
flag=1;//只要有一点不符合入度为零，就为不合法
}
if(flag)
ans.push_back(i);
}
cout<<ans[0];
for(int i=1; i<ans.size(); ++i)
cout<<" "<<ans[i];
return 0;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/136498.html原文链接：https://javaforall.net
