Advertisement
Josif_tepe

Untitled

Jun 9th, 2022
922
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.61 KB | None
  1. #include <iostream>
  2. #include <vector>
  3. #include <cstring>
  4. #include <algorithm>
  5. #include <stack>
  6. using namespace std;
  7. int n, m;
  8. vector<int>graph[100005];
  9. vector<int>rev_graph[100005];
  10. vector<int> v;
  11. bool visited[100005];
  12.  
  13. stack<int>s;
  14.  
  15. void dfs(int node){
  16. visited[node]=true;
  17. for(int i=0; i<graph[node].size(); i++){
  18.     int sosed=graph[node][i];
  19.     if(!visited[sosed]){
  20.         dfs(sosed);
  21.     }
  22. }
  23. s.push(node);
  24. }
  25.  
  26. void rev_dfs(int node){
  27. visited[node]=true;
  28.     v.push_back(node);
  29. for(int i=0; i<rev_graph[node].size(); i++){
  30.     int rev_sosed=rev_graph[node][i];
  31.     if(!visited[rev_sosed]){
  32.         rev_dfs(rev_sosed);
  33.     }
  34. }
  35. }
  36. bool special[100005];
  37. int main()
  38. {
  39.  
  40. cin>>n>>m;
  41. for(int i=0; i<m; i++){
  42.     int a, b;
  43.     cin>>a>>b;
  44.     graph[a].push_back(b);
  45.     rev_graph[b].push_back(a);
  46. }
  47.     memset(visited, false, sizeof visited);
  48.     memset(special, false, sizeof special);
  49.     for(int i=1; i<=n; i++){
  50.         if(!visited[i]){
  51.             dfs(i);
  52.         }
  53.     }
  54.     memset(visited, false, sizeof visited);
  55.     while(!s.empty()){
  56.         int node=s.top();
  57.         if(!visited[node]){
  58.             v.clear();
  59.             rev_dfs(node);
  60. //            cout << v.size() << endl;
  61.             if(v.size() > 1) {
  62.                 for(int p = 0; p < v.size(); p++) {
  63.                     special[v[p]] = true;
  64.                 }
  65.             }
  66.         }
  67.         s.pop();
  68.     }
  69.  
  70.     for(int i=1; i<=n; i++){
  71. //            cout<<v[i];
  72.         if(special[i]){
  73.             cout<<1 << " ";
  74.         }
  75.         else{
  76.              cout<<0 << " ";
  77.         }
  78.     }
  79.     return 0;
  80. }
  81.  
Advertisement
RAW Paste Data Copied
Advertisement