matbensch

Toposort C++

Jan 19th, 2023
181
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.63 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4.  
  5. using namespace std;
  6.  
  7. int n;
  8. vector<vector<int>> adj;
  9. vector<bool> vis;
  10. vector<int> L;
  11.  
  12. void dfs(int u)
  13. {
  14.     vis[u] = true;
  15.     for(int v:adj[u]) if(!vis[v]) dfs(v);
  16.     L.push_back(u);
  17. }
  18.  
  19. void toposort()
  20. {
  21.     for(int i=0;i<n;i++) if(!vis[i]) dfs(i);
  22.     reverse(L.begin(), L.end());
  23. }
  24.  
  25. int main()
  26. {
  27.     n = 7;
  28.     vis.resize(n);
  29.     adj = {
  30.         {1},
  31.         {2,3,4},
  32.         {4},
  33.         {4},
  34.         {5},
  35.         {},
  36.         {3}
  37.     };
  38.     toposort();
  39.     cout << "Toposort: ";
  40.     for(int e:L) cout << e << " ";
  41.     cout << '\n';
  42. }
Advertisement
Add Comment
Please, Sign In to add comment