fork download
copy 
  1. /// slt by muoii
  2. /// vn.spoj.com/problems/SAFENET2/
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5. #define tag "spoj"
  6. #define maxn 1007
  7. #define maxc 207
  8. #define oo 1000000007
  9. #define mid ((l+r)>>1)
  10. #define meset(a,x) memset(a,x,sizeof(a))
  11. #define loop(x) for(int LoOpEr=x;LoOpEr-->0;)
  12. ///>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
  13. int ans;
  14. int numbering;
  15. int n,m;
  16. vector< vector<int> > adj;
  17. vector<int> num,low;
  18. vector<int> par;
  19. stack<int> stak;
  20.  
  21. /// par[v]=u:   cut[u]=true <->  nchild(u)>=2 || num[u]<=low[v]
  22.  
  23. void slt(const int &u,const int &parent)
  24. {
  25.     par[u]=parent;
  26.     num[u]=++numbering;
  27.     low[u]=oo;
  28.  
  29.     for(const int &v: adj[u])
  30.         if(par[v]<0)
  31.         {
  32.             stak.push(v);
  33.             slt(v,u);
  34.             low[u]=min(low[u],low[v]);
  35.  
  36.             if(num[u]<=low[v])
  37.             {
  38.                 int cnt=1;
  39.                 while(stak.top()!=v) ++cnt,stak.pop();
  40.                 ++cnt,stak.pop();
  41.  
  42.                 ans=max(ans,cnt);
  43.             }
  44.         }
  45.         else if(v!=parent) low[u]=min(low[u],num[v]);
  46.  
  47.     if(num[u]==numbering) ans=max(ans,1);
  48. }
  49. int main()
  50. {
  51.     #ifdef dmdd
  52.     freopen(tag".inp","r",stdin); freopen(tag".out","w",stdout);
  53.     #endif // dmdd
  54.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  55.     cin>>n>>m;
  56.  
  57.     ///load graph:
  58.     adj.resize(n+1);par.resize(n+1,-1);num.resize(n+1);low.resize(n+1);
  59.     int x,y;
  60.     while(m-->0) cin>>x>>y,adj[x].push_back(y),adj[y].push_back(x);
  61.  
  62.     ///find answer:
  63.     for(int i=1;i<=n;i++)
  64.         if(par[i]<0)
  65.             slt(i,0);
  66.  
  67.     cout<<ans;
  68.  
  69.     return 0;
  70. }
  71.  
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
8 10
1 2
2 3
3 1
1 4
4 5
5 1
1 6
6 7
7 8
8 1
stdout
copy 
4
https://ideone.com/9pUGRs
language:
C++14 (gcc 8.3)
created:
6 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!