该题大意就是给出几条有向边和相应点的排序,判断这样的点是否合理。
开始时用了hash数组记录有向边,发现出错,后来知道了需要判重,开始真的难到了。可仔细观察map数组,主意就来了,程序如下:
#include<iostream> using namespace std; bool map[1002][1002]; int p[1002],hh[1002]; int main() { int n,i,a,b,j,m; scanf("%d %d",&n,&m); for(i=1;i<=n;i++) for(j=1;j<=n;j++) map[i][j]=false; memset(hh,0,sizeof(hh)); for(i=0;i<m;i++) { scanf("%d %d",&a,&b); map[a][b]=true; } for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(map[i][j])hh[j]++; int ff=0; for(i=1;i<=n;i++) { scanf("%d",&p[i]); if(ff==0) { if(hh[p[i]])ff=1; else { for(j=1;j<=n;j++) { if(map[p[i]][j]) { map[p[i]][j]=false; hh[j]--; } } } } } if(ff) { printf("NO\n"); } else { printf("YES\n"); } return 0; }