AcWing 1639. 拓扑顺序
原题链接
简单
作者:
RainSure
,
2022-03-01 09:29:18
,
所有人可见
,
阅读 226
判断拓扑排序 要求每条边的起点比终点在拓扑排序中更靠前
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
const int N = 1010, M = 10010;
PII edges[M];
int p[N];
int n, m;
int main()
{
cin >> n >> m;
for(int i = 0; i < m; i ++) cin >> edges[i].x >> edges[i].y;
int k; cin >> k;
vector<int> res;
for(int i = 0; i < k; i ++){
bool flag = true;
for(int j = 1; j <= n; j ++){
int x; cin >> x;
p[x] = j;
}
for(int j = 0; j < m; j ++){
if(p[edges[j].x] > p[edges[j].y]){
flag = false;
break;
}
}
if(!flag) res.push_back(i);
}
for(int i = 0; i < res.size(); i ++){
if(i != 0) cout << " ";
cout << res[i];
}
return 0;
}