fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. bool flag[1005][1005];
  5. int cnt[1005],ara[1005];
  6. vector <int> edges[1005];
  7. multiset <int> indeg;
  8. multiset <int>:: iterator it;
  9. int main ()
  10. {
  11.     int i,u,v,m,n,t,j,s;
  12.     bool chk=true;
  13.  
  14.     scanf ("%d %d",&n,&m);
  15.     for (i=0;i<m;i++) {
  16.         scanf ("%d %d",&u,&v);
  17.         if (!flag[u][v]) {
  18.             edges[u].push_back(v);
  19.             cnt[v]++;
  20.             flag[u][v]=true;
  21.         }
  22.         if (flag[v][u]) chk=false;
  23.     }
  24.     for (i=1;i<=n;i++) indeg.insert(cnt[i]);
  25.     for (i=1;i<=n;i++) scanf ("%d",&ara[i]);
  26.  
  27.     if (chk) for (i=1;i<=n;i++) {
  28.         u=ara[i];
  29.         it=indeg.begin();
  30.         if (cnt[u]!=*it) {
  31.             chk=false;
  32.             break;
  33.         }
  34.         indeg.erase(it);
  35.         t=edges[u].size();
  36.         for (j=0;j<t;j++) {
  37.             v=edges[u][j];
  38.             indeg.erase(cnt[v]);
  39.             cnt[v]--;
  40.             indeg.insert(cnt[v]);
  41.         }
  42.     }
  43.  
  44.     if (chk) cout<<"YES";
  45.     else cout<<"NO";
  46.  
  47.     return 0;
  48. }
Success #stdin #stdout 0s 17080KB
comments (?)
stdin
copy 
3 3
1 3
3 2
2 1
1 3 2
stdout
copy 
YES
https://ideone.com/ZljGZ5
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!