Advertisement
Josif_tepe

Untitled

Dec 26th, 2022
1,140
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.46 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <set>
  4. #include <cstring>
  5. #include <queue>
  6. #include <cmath>
  7. #include <algorithm>
  8. #include <stack>
  9. using namespace std;
  10. const int maxn = 1e5 + 10;
  11. int n, m;
  12. vector<int> graph[maxn], reversed_graph[maxn];
  13. bool visited[maxn];
  14. stack<int> st;
  15. void topological_sort(int node) {
  16.     visited[node] = true;
  17.     for(int i = 0; i < (int) graph[node].size(); i++) {
  18.         int neighbour = graph[node][i];
  19.         if(!visited[neighbour]) {
  20.             topological_sort(neighbour);
  21.         }
  22.     }
  23.    
  24.     st.push(node);
  25. }
  26. void dfs(int node) {
  27.     cout << node + 1 << " " ;
  28.     visited[node] = true;
  29.     for(int i = 0; i < (int) reversed_graph[node].size(); i++) {
  30.         int neighbour = reversed_graph[node][i];
  31.         if(!visited[neighbour]) {
  32.             dfs(neighbour);
  33.         }
  34.     }
  35. }
  36. int main() {
  37.     cin >> n >> m;
  38.     for(int i = 0; i < m; i++) {
  39.         int a, b;
  40.         cin >> a>> b;
  41.         a--;
  42.         b--;
  43.         graph[a].push_back(b);
  44.         reversed_graph[b].push_back(a);
  45.     }
  46.     memset(visited, false, sizeof visited);
  47.     for(int i = 0; i < n; i++) {
  48.         if(!visited[i]) {
  49.             topological_sort(i);
  50.         }
  51.     }
  52.    
  53.     memset(visited, false, sizeof visited);
  54.     while(!st.empty()) {
  55.         int node = st.top();
  56.         st.pop();
  57.         if(!visited[node]) {
  58.             dfs(node);
  59.             cout << endl;
  60.         }
  61.        
  62.     }
  63.     return 0;
  64. }
  65.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement