Advertisement
Josif_tepe

Untitled

Mar 6th, 2023
841
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.24 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <stack>
  4. #include <algorithm>
  5. #include <cstring>
  6.  
  7. using namespace std;
  8. int m;  int n;
  9. bool visited[300005];
  10. stack<int>s;
  11. vector<int>graph[300005];
  12. vector<int>rev_graph[300005];
  13. void dfs(int node){
  14. visited[node]=true;
  15. for(int i=0; i<graph[node].size(); i++){
  16.  int sosed=graph[node][i];
  17.  if(visited[sosed]==false){
  18.     dfs(sosed);
  19. }
  20.  
  21. }
  22.     s.push(node);
  23. }
  24. void rev_dfs(int r_node){
  25. visited[r_node]=true;
  26. cout<<r_node<<" ";
  27. for(int i=0; i<rev_graph[r_node].size(); i++){
  28.  int rev_sosed=rev_graph[r_node][i];
  29.  if(visited[rev_sosed]==false){
  30.     rev_dfs(rev_sosed);
  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.            
  44.         graph[b].push_back(a);
  45.         rev_graph[a].push_back(b);
  46.     }
  47.     memset(visited,  false, sizeof visited);
  48.  
  49.     for(int i=0; i<n; i++){
  50.         if(visited[i]==false){
  51.             dfs(i);
  52.         }
  53.     }
  54.     memset(visited,false , sizeof visited);
  55.     while(!s.empty()){
  56.         int node=s.top();
  57.         if(visited[node]==false){
  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