Advertisement
zydhanlinnar11

Topo Topo

May 28th, 2022
475
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // Tested by zydhanlinnar11 on May 28, 2022
  2. #include <iostream>
  3. #include <vector>
  4. #include <stack>
  5. #include <cassert>
  6. using namespace std;
  7. typedef vector<int> vi;
  8. typedef vector<vi> vvi;
  9. typedef stack<int> si;
  10.  
  11. bool dfs(vvi &adjList, vi &state, si &vertex, int dst) {
  12.     if(state[dst] == 1)
  13.         return false;
  14.     if(state[dst] == 2)
  15.         return true;
  16.     state[dst] = 1;
  17.     bool ret = true;
  18.     for(int i=0; i < adjList[dst].size() && ret; i++)
  19.         ret &= dfs(adjList, state, vertex, adjList[dst][i]);
  20.     state[dst] = 2;
  21.     vertex.push(++dst);
  22.     return ret;
  23. }
  24.  
  25. bool topsort(vvi &adjList, vi &state, si &vertex, int n) {
  26.     for(int i=0; i<n; i++)
  27.         if(state[i] != 2 && !dfs(adjList, state, vertex, i))
  28.             return false;
  29.     return true;
  30. }
  31.  
  32. int main() {
  33.     #ifdef ZYD_WSL
  34.         freopen("/home/zydhanlinnar11/prakfinal-qa/in", "r", stdin);
  35.     #endif
  36.     ios_base::sync_with_stdio(false); cin.tie(NULL);
  37.     int n, m;
  38.     cin>>n>>m;
  39.     assert(n == (int)1e5 && m == (int)1e5);
  40.     assert(1 <= n && n <= (int)1e5);
  41.     assert(1 <= m && m <= (int)1e5);
  42.     vvi adjList(n); vi state(n, 0); si vertex;
  43.     for(int i=0; i<m; i++) {
  44.         int src, dst;
  45.         cin>>src>>dst;
  46.         assert(1 <= src && src <= n);
  47.         assert(1 <= dst && dst <= n);
  48.         src--, dst--;
  49.         adjList[src].push_back(dst);
  50.     }
  51.     if(topsort(adjList, state, vertex, n))
  52.         for(int i=0; i<n; i++) {
  53.             cout<<vertex.top()<<" \n"[i == n - 1];
  54.             vertex.pop();
  55.         }
  56.     else cout<<"-1\n";
  57.     return 0;
  58. }
Advertisement
RAW Paste Data Copied
Advertisement