fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define for1(i,m,n) for(int i=m;i<=n;i++)
  5. #define for0(i,m,n) for(int i=m;i<n;i++)
  6.  
  7. #define int unsigned long long
  8. #define el '\n'
  9. #define fi first
  10. #define se second
  11. #define ii pair<int,int>
  12. #define vll(i) i.begin(),i.end()
  13. #define pb push_back
  14.  
  15. const int N=5*1e5+1111;
  16. const int mod=1e9+7;
  17. int id=0,id_=0;
  18. int n,m,k,l;
  19. vector<int> v[N],v_[N];
  20. int num[N],a[N],b[N],low[N],color[N],in[N];
  21. // a:tong phan tu;
  22. stack<int>st;
  23. void solve(int u){
  24. num[u]=low[u]=++id;
  25. color[u]=1;
  26. in[u]=1;
  27. st.push(u);
  28. //if(u==8) cout<<"hi"<<el;
  29.    for(auto x:v[u]){
  30.  
  31.  
  32.       if(color[x]==0){
  33.            //   if(u==8) cout<<"hi"<<x<<' '<<num[x]<<' '<<color[x]<<' '<<low[x]<<el;
  34.         solve(x);
  35.         low[u]=min(low[u],low[x]);
  36.               }
  37.       else if(in[x]) {
  38.             low[u]=min(low[u],num[x]);
  39.            // if(u==8) cout<<"hi"<<x<<' '<<num[x]<<' '<<color[x]<<' '<<low[x]<<el;
  40.       }
  41.  
  42.  
  43.     //num[x]=1;
  44.  
  45.    }
  46.  
  47.   // cout<<"hi"<<u<<' '<<b[u]<<el;
  48.  
  49.    if(num[u]==low[u]){
  50.  
  51.         id_++;
  52.        while(st.top()!=u){
  53.         v_[id_].pb(st.top());
  54.         in[st.top()]=0;
  55.         st.pop();
  56.  
  57.       }
  58.     v_[id_].pb(u);
  59.     in[u]=0;
  60.    st.pop();
  61.       }
  62.  
  63.   // cout<<a[u]<<' '<<b[u]<<el;
  64. }
  65.  
  66.  
  67. signed main(){
  68.   ios_base::sync_with_stdio(0);
  69.   cin.tie(0);
  70.   cout.tie(0);
  71.   // freopen("bai1.INP","r",stdin);
  72.   // freopen("bai1.OUT","w",stdout);
  73.    cin>>n>>m;
  74.  
  75.  
  76.  
  77.    for1(i,1,m){
  78.       int x,y;cin>>x>>y;
  79.       v[x].pb(y);
  80.          }
  81.  
  82.  
  83. for1(i,1,n){
  84.  if(color[i]==0){
  85.     solve(i);
  86.  }
  87. }
  88.  
  89.  
  90. cout<<id_<<el;
  91.  
  92. for1(i,1,id_){
  93.  
  94. for(auto x:v_[i]){
  95.   cout<<x<<' ';
  96. }
  97.   cout<<el;
  98. }
  99.     return 0;
  100. }
  101.  
Success #stdin #stdout 0.01s 27860KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/lsLtdg
thanh phan lien thong manh
language:
C++14 (gcc 8.3)
created:
14 days 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!