fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef pair<int,int>   II;
  4. typedef vector< II >      VII;
  5. typedef vector<int>     VI;
  6. typedef vector< VI > 	VVI;
  7. typedef long long int 	LL;
  8. #define PB push_back
  9. #define MP make_pair
  10. #define F first
  11. #define S second
  12. #define SZ(a) (int)(a.size())
  13. #define ALL(a) a.begin(),a.end()
  14. #define SET(a,b) memset(a,b,sizeof(a))
  15. #define si(n) scanf("%d",&n)
  16. #define dout(n) printf("%d\n",n)
  17. #define sll(n) scanf("%lld",&n)
  18. #define lldout(n) printf("%lld\n",n)
  19. #define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)
  20. #define TRACE
  21. #ifdef TRACE
  22. #define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
  23. template <typename Arg1>
  24. void __f(const char* name, Arg1&& arg1){
  25. 	cerr << name << " : " << arg1 << std::endl;
  26. }
  27. template <typename Arg1, typename... Args>
  28. void __f(const char* names, Arg1&& arg1, Args&&... args){
  29. 	const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
  30. }
  31. #else
  32. #define trace(...)
  33. #endif
  34. //FILE *fin = freopen("in","r",stdin);
  35. //FILE *fout = freopen("out","w",stdout);
  36. const int N = int(1e5)+1;
  37. const int M = int(2e5)+1;
  38. VI g[N],rg[N],comp,order;
  39. int vis[N],ans[N];
  40. void dfs1(int u)
  41. {
  42.     vis[u]=1;
  43.     for(int i=0;i<SZ(g[u]);i++)
  44.         if(!vis[g[u][i]])
  45.             dfs1(g[u][i]);
  46.     order.PB(u);
  47. }
  48. void dfs2(int u)
  49. {
  50.     vis[u]=1;comp.PB(u);
  51.     for(int i=0;i<SZ(rg[u]);i++)
  52.         if(!vis[rg[u][i]])
  53.             dfs2(rg[u][i]);
  54. }
  55. int main()
  56. {
  57.     int n,m;
  58.     si(n);si(m);
  59.     for(int i=0;i<m;i++)
  60.     {
  61.         int u,v;
  62.         si(u);si(v);
  63.         g[u].PB(v);
  64.         rg[v].PB(u);
  65.     }
  66.     for(int i=1;i<=n;i++)
  67.         if(!vis[i])
  68.             dfs1(i);
  69.     SET(vis,0);
  70.     for(int i=1;i<=n;i++)
  71.     {
  72.         int v = order[n-i];
  73.         if(!vis[v])
  74.         {
  75.             dfs2(v);
  76.             if(SZ(comp)>1)
  77.                 for(auto &it:comp)
  78.                     ans[it]=1;
  79.             comp.clear();
  80.         }
  81.     }
  82.     for(int i=1;i<=n;i++)printf("%d ",ans[i]);
  83.     printf("\n");
  84. 	return 0;
  85. }
Success #stdin #stdout 0s 6600KB
comments (?)
stdin
copy 
5 5
1 2 
2 3 
3 4 
4 5
4 2
stdout
copy 
0 1 1 1 0
https://ideone.com/2SE16N
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!