fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define int long long
  3. using namespace std;
  4. int n,m;
  5. vector<int>p[200001];
  6. int low[200001],num[200001],dele[200001],scc=0,cc=1;
  7. stack<int>st;
  8. void nhap()
  9. {
  10.     cin>>n>>m;
  11.     for (int i=1;i<=m;i++)
  12.     {
  13.         int a,b;
  14.         cin>>a>>b;
  15.         p[a].push_back(b);
  16.     }
  17. }
  18. void dfs(int u)
  19. {
  20.     low[u]=num[u]=cc++;
  21.     st.push(u);
  22.     for (int v:p[u])
  23.     {
  24.         if (dele[v]) continue;
  25.         if (!num[v])
  26.         {
  27.             dfs(v);
  28.             low[u]=min(low[u],low[v]);
  29.         }
  30.         else low[u]=min(low[u],num[v]);
  31.     }
  32.     if (low[u]==num[u])
  33.     {
  34.         scc++;
  35.         while (true)
  36.         {
  37.             int v=st.top();
  38.             st.pop();
  39.             dele[v]=scc;
  40.             if (v == u) break;
  41.         }
  42.     }
  43. }
  44. signed main()
  45. {
  46.     nhap();
  47.     for (int i=1;i<=n;i++)
  48.     {
  49.         if (!num[i]) dfs(i);
  50.     }
  51.     cout<<scc<<"\n";
  52.     for (int i=1;i<=n;i++)
  53.     {
  54.         cout<<dele[i]<<" ";
  55.     }
  56. }
  57.  
Success #stdin #stdout 0.01s 9784KB
comments (?)
stdin
copy 
5 6
1 2
2 3
3 1
3 4
4 5
5 4
stdout
copy 
2
2 2 2 1 1
https://ideone.com/07ZTy0
language:
C++14 (clang 8.0)
created:
61 days ago
visibility:
secret

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!