SuitNdtie

Food web

Apr 15th, 2019
144
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.74 KB | None | 0 0
  1. #include<stdio.h>
  2. #include<vector>
  3. #include<stack>
  4. using namespace std;
  5. int n,m;
  6. vector<int> adj[100010];
  7. int color[100010];
  8. bool iscycle = false;
  9. stack<int> ans;
  10. void DFS(int u){
  11.     if(color[u] == 2){
  12.         return;
  13.     }
  14.     if(color[u] == 1){
  15.         iscycle = true;
  16.         return;
  17.     }
  18.     color[u] = 1;
  19.     for(int i=0;i<adj[u].size();i++){
  20.         int v = adj[u][i];
  21.         DFS(v);
  22.     }
  23.     color[u] = 2;
  24.     ans.push(u);
  25. }
  26.  
  27. int main()
  28. {
  29.     scanf("%d %d",&n,&m);
  30.    
  31.     for(int i=0;i<m;i++){
  32.         int u,v;
  33.         scanf("%d %d",&v,&u);
  34.         adj[u].push_back(v);
  35.     }
  36.     for(int i=1;i<=n;i++){
  37.         if(color[i] == 0){
  38.             DFS(i);
  39.         }
  40.     }
  41.     if(!iscycle){
  42.         printf("Yes\n");
  43.         while(!ans.empty()){
  44.             printf("%d ",ans.top());
  45.             ans.pop();
  46.         }
  47.     }
  48.     else{
  49.         printf("No");
  50.     }
  51.     return 0;
  52. }
Advertisement
Add Comment
Please, Sign In to add comment