Advertisement
Josif_tepe

Untitled

May 18th, 2022
509
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <queue>
  3. #include <cstring>
  4. #include <stack>
  5. using namespace std;
  6. typedef long long ll;
  7. int n, m;
  8. vector<int> graph[1005], rev_graph[1005];
  9. stack<int> st;
  10. bool visited[1005];
  11.  
  12. void dfs(int node) {
  13.     visited[node] = true;
  14.     for(int i = 0; i < graph[node].size(); i++) {
  15.         int sosed = graph[node][i];
  16.         if(!visited[sosed])
  17.             dfs(sosed);
  18.     }
  19.     st.push(node);
  20. }
  21. void rev_dfs(int node) {
  22.     visited[node] = true;
  23.     cout << node << " ";
  24.     for(int i = 0; i < rev_graph[node].size(); i++) {
  25.         int sosed = rev_graph[node][i];
  26.         if(!visited[sosed]) {
  27.             rev_dfs(sosed);
  28.         }
  29.     }
  30. }
  31. int main() {
  32.     ios_base::sync_with_stdio(false);
  33.     cin >> n >> m;
  34.    
  35.     for(int i = 0; i < m; i++) {
  36.         int a, b;
  37.         cin >> a >> b;
  38.         graph[a].push_back(b);
  39.         rev_graph[b].push_back(a);
  40.     }
  41.     memset(visited, false, sizeof visited);
  42.     for(int i = 0; i < n; i++) {
  43.         if(!visited[i]) {
  44.             dfs(i);
  45.         }
  46.     }
  47.     memset(visited, false, sizeof visited);
  48.     while(!st.empty()) {
  49.         int node = st.top();
  50.         if(!visited[node]) {
  51.             rev_dfs(node);
  52.             cout << endl;
  53.         }
  54.         st.pop();
  55.     }
  56.     return 0;
  57. }
  58.  
Advertisement
RAW Paste Data Copied
Advertisement