ccbeginner

OKGOOGLE

Feb 29th, 2020
51
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /******************************************************************************
  2.  
  3.                               Online C++ Compiler.
  4.                Code, Compile, Run and Debug C++ program online.
  5. Write your code in this editor and press "Run" button to compile and execute it.
  6.  
  7. *******************************************************************************/
  8.  
  9. #include <bits/stdc++.h>
  10. using namespace std;
  11.  
  12. int low[100001];
  13. int depth[100001];
  14. int parrent[100001];
  15. bool ans[100001];
  16.  
  17. vector<int> v[100001];
  18. void dfs(int d, int u){
  19.     depth[u] = low[u] = d;
  20.     for(unsigned i = 0; i < v[u].size(); ++i){
  21.         int cur = v[u][i];
  22.         if(depth[cur] == 0)dfs(d+1, cur);
  23.         if(low[u] > low[cur]){
  24.             low[u] = low[cur];
  25.             parrent[u] = parrent[cur];
  26.             ans[u] = ans[parrent[u]] = 1;
  27.         }
  28.     }
  29. }
  30.  
  31. int main(){
  32.     int n,m;
  33.     cin >> n >> m;
  34.     for(int i = 0; i < m; ++i){
  35.         int a,b;
  36.         cin >> a >> b;
  37.         v[a].emplace_back(b);
  38.     }
  39.     for(int i = 1; i <= n; ++i)parrent[i] = i;
  40.     for(int i = 1; i <= n; ++i){
  41.         if(depth[i] == 0)dfs(1, i);
  42.     }
  43.     for(int i = 1; i <= n; ++i){
  44.         if(i != 1)cout << ' ';
  45.         cout << ans[i];
  46.     }
  47.     cout << '\n';
  48.     return 0;
  49. }
RAW Paste Data