DontCallMeNuttoPleas

FoodWeb

Mar 27th, 2020
152
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.06 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using pii=pair<int,int>;
  4. bool check=0;
  5. vector<int> H[100010];
  6. bool v[100010];
  7.  
  8. void DFS(int i){
  9.     v[i]=1;
  10.     for(auto x:H[i]){
  11.         if(v[x]){
  12.             check=1;
  13.             return;
  14.         }else DFS(x);
  15.         if(check==1) return;
  16.     }
  17.     v[i]=0;
  18. }
  19.  
  20. int main(){
  21.     int V,E,h,p;
  22.     scanf("%d%d",&V,&E);
  23.     vector<bool> visited(V+10,false);
  24.     vector<int> hunted(V+10,0);
  25.     queue<int> Q;
  26.     priority_queue<pii,vector<pii>,greater<pii>> q;
  27.     for(int i=0;i<E;i++){
  28.         scanf("%d%d",&p,&h);
  29.         H[h].push_back(p);
  30.         hunted[p]++;
  31.     }
  32.     for(int i=1;i<=V;i++){
  33.         check=0;
  34.         DFS(i);
  35.         if(check==1) break;
  36.     }
  37.     if(check==1){
  38.         printf("No");
  39.         return 0;
  40.     }
  41.     for(int i=1;i<=V;i++){
  42.         if(hunted[i]==0){
  43.             q.push({0,i});
  44.             while(!q.empty()){
  45.                 int r=q.top().first;
  46.                 int c=q.top().second;
  47.                 Q.push(c);
  48.                 q.pop();
  49.                 visited[c]=true;
  50.                 for(auto x:H[c]){
  51.                     if(hunted[x]>1){
  52.                         hunted[x]--;
  53.                         continue;
  54.                     }else q.push({r+1,x});
  55.                 }
  56.             }
  57.         }
  58.     }
  59.     printf("Yes\n");
  60.     while(!Q.empty()){
  61.         printf("%d ",Q.front());
  62.         Q.pop();
  63.     }
  64. }
Advertisement
Add Comment
Please, Sign In to add comment