Advertisement
YEZAELP

o22_oct_topo

Jan 17th, 2022
676
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.00 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. const int N = 1e5 + 10;
  5. vector <int> g[N];
  6. int color[N], indeg[N];
  7. bool vs[N];
  8.  
  9. bool cycle(int u){
  10.     if(color[u] == 1)
  11.         return true;
  12.     if(color[u] == 2)
  13.         return false;
  14.     color[u] = 1;
  15.     for(auto v: g[u]){
  16.         if(cycle(v))
  17.             return true;
  18.     }
  19.     color[u] = 2;
  20.     return false;
  21. }
  22.  
  23. int main(){
  24.  
  25.     int n, m;
  26.     scanf("%d %d", &n, &m);
  27.  
  28.     for(int i=1;i<=m;i++){
  29.         int u, v;
  30.         scanf("%d %d", &u, &v);
  31.         g[u].push_back(v);
  32.         indeg[v] ++;
  33.     }
  34.  
  35.     if(cycle(1)){
  36.         printf("no");
  37.         return 0;
  38.     }
  39.  
  40.     queue <int> q;
  41.     for(int u=1;u<=n;u++){
  42.         if(indeg[u] == 0)
  43.             q.push(u);
  44.     }
  45.  
  46.     while(!q.empty()){
  47.         int u = q.front();
  48.         q.pop();
  49.         printf("%d\n", u);
  50.         for(auto v: g[u]){
  51.             indeg[v] --;
  52.             if(indeg[v] == 0 and !vs[v])
  53.                 q.push(v);
  54.         }
  55.     }
  56.  
  57.     return 0;
  58. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement