Advertisement
Josif_tepe

Untitled

May 18th, 2022
718
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.21 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <stack>
  4. //#include <bits/stdc++.h>
  5. using namespace std;
  6. int n, m;
  7. vector<int>graph[3005];
  8. vector<int>rev_graph[3005];
  9. bool visited[3005];
  10. stack<int>s;
  11. void dfs(int node){
  12.  
  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.    
  20. }
  21.     s.push(node);
  22. }
  23. void rev_dfs(int node){
  24. visited[node]=true;
  25. cout<<node<<" ";
  26. for(int i=0; i<rev_graph[node].size(); i++){
  27.     int rev_sosed=rev_graph[node][i];
  28.     if(!visited[rev_sosed]){
  29.         rev_dfs(rev_sosed);
  30.     }
  31. }
  32. }
  33.  
  34.  
  35. int main()
  36. {
  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.         rev_graph[b].push_back(a);
  45.     }
  46.     memset(visited, false, sizeof visited);
  47.  
  48.     for(int i=0; i<n; i++){
  49.         if(!visited[i]){
  50.             dfs(i);
  51.         }
  52.     }
  53.     memset(visited, false, sizeof visited);
  54.     while(!s.empty()){
  55.         int node=s.top();
  56. //        cout << node << endl;
  57.         if(!visited[node]){
  58.             rev_dfs(node);
  59.             cout<<endl;
  60.         }
  61.         s.pop();
  62.     }
  63.     return 0;
  64. }
  65.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement