kananasgarli90

topological sort

Sep 14th, 2020
781
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int n, m, color[100001], dis[100001], fin[100001], t, u, v, say;
  5.  
  6. vector<int>adj[100001];
  7. void dfs(int s){
  8.     color[s] = 1;
  9.     for(int i = 0; i < adj[s].size(); i++){
  10.         int x = adj[s][i];
  11.         if(color[x] == 0){
  12.             dfs(x);
  13.         }
  14.         if(color[x] == 1){
  15.             say = 1;
  16.             return;
  17.         }
  18.     }
  19.     color[s] = 2;
  20.     fin[++t] = s;
  21. }
  22. int main()
  23. {
  24.     cin>>n>>m;
  25.     while(m--){
  26.         cin>>u>>v;
  27.         adj[u].push_back(v);
  28.     }
  29.     for(int i = 1; i <= n; i++){
  30.         if(color[i] == 0){
  31.             dfs(i);
  32.         }
  33.     }
  34.     if(say == 1){
  35.         cout<<-1<<endl;
  36.     }
  37.     else{
  38.         for(int i = t; i >= 1; i--){
  39.             cout<<fin[i]<<" ";
  40.         }
  41.     }
  42. }
  43.  
RAW Paste Data