Advertisement
Oppenheimer

Topological sort dfs

Aug 20th, 2022 (edited)
129
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.63 KB | None | 0 0
  1. // Topological osrt may or may not be unique .. goes from vertice having least influx to highest influx
  2. // used in prerequistes course type questions
  3.  
  4. int n; // number of vertices
  5. vector<vector<int>> adj; // adjacency list of graph
  6. vector<bool> visited;
  7. vector<int> ans;
  8.  
  9. void dfs(int v) {
  10.     visited[v] = true;
  11.     for (int u : adj[v]) {
  12.         if (!visited[u])
  13.             dfs(u);
  14.     }
  15.     ans.push_back(v);
  16. }
  17.  
  18. void topological_sort() {
  19.     visited.assign(n, false);
  20.     ans.clear();
  21.     for (int i = 0; i < n; ++i) {
  22.         if (!visited[i])
  23.             dfs(i);
  24.     }
  25.     reverse(ans.begin(), ans.end());
  26. }
  27.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement