题目链接：点击打开链接
题目大意：判断以下序列是否符合拓扑排序定义，若不符合，输出第 i-th 的序列对应的 i。
解题思路：模拟 Topo 排序。
AC 代码
#include<bits/stdc++.h> #include<cmath> #define mem(a,b) memset(a,b,sizeof a) #define ssclr(ss) ss.clear(), ss.str("") #define INF 0x3f3f3f3f #define MOD 1000000007 using namespace std; typedef long long ll; const int NV=1e3+10; int n; int in[NV], tin[NV]; int mp[NV][NV]; set<int> st; void init() { st.clear(); for(int i=1;i<=n;i++) { tin[i]=in[i]; if(in[i]==0) { st.insert(i); } } } int main() { int m,q,a,u,v,first=1; scanf("%d%d",&n,&m); for(int i=0;i<m;i++) { scanf("%d%d",&u,&v); if(!mp[u][v]) { mp[u][v]=1; in[v]++; } } scanf("%d",&q); for(int i=0;i<q;i++) { int f=1; init(); for(int j=0;j<n;j++) { scanf("%d",&a); auto it=st.find(a); if(it!=st.end()) { st.erase(it); for(int k=1;k<=n;k++) { if(mp[a][k]==1) { tin[k]--; if(tin[k]==0) st.insert(k); } } } else f=0; } if(!f) if(first) first=0, printf("%d",i); else printf(" %d",i); } puts(""); return 0; }
