fork download
copy 
  1. /// cut&bridge by muoii
  2. /// vn.spoj.com/problems/GRAPH_/
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5. #define tag "main"
  6. #define maxn 10007
  7. #define oo 1000000007LL
  8. #define mid ((l+r)>>1)
  9. #define getbit(x,i) ((x)>>(i)&1)
  10. #define onbit(x,i) ((x)|(1<<(i)))
  11. #define offbit(x,i) ((x)&~(1<<(i)))
  12. #define cntbit(x) (__builtin_popcountll(x))
  13. #define meset(a,x) memset(a,x,sizeof(a))
  14. #define forinc(i,a,b) for(int i=a;i<=b;i++)
  15. #define fordec(i,a,b) for(int i=a;i>=b;i--)
  16. #define debug(x) cerr<<#x<<" = "<<x<<"\n"
  17. #define runtime(stime) ((clock() - stime) / CLOCKS_PER_SEC * 1000)
  18. #define checkfile(FiLeNaMe) { if(fopen(FiLeNaMe".inp","r")) freopen(FiLeNaMe".inp","r",stdin),freopen(FiLeNaMe".out","w",stdout); }
  19. template<typename T> inline void inp(T &x) { static char k; static bool neg; while((k=getchar())!='-' && !isdigit(k)); neg = k=='-'; x=(neg=k=='-')?0:k-48; while(isdigit(k=getchar())) x = (x<<3) + (x<<1) +  k-48; x=neg?-x:+x; }
  20. template<typename T> inline void out(T x) { if(x<0) putchar('-'),x=-x; if(x>9) out(x/10); putchar(x%10+48); }
  21. #define space putchar(' ')
  22. #define endline putchar('\n')
  23. #define inpint ({ int x; inp(x); x; })
  24. #define inpchar ({ char k; while((k=getchar())==' ' || k=='\n'); k; })
  25. #define inpstr ({ char k; while((k=getchar())==' ' || k=='\n'); string s=""; s+=k; while((k=getchar())!=' ' && k!='\n') s+=k; s; })
  26.  
  27. /// --------------------------------------------------------------------------------------------------------------------------------
  28. #define long long long
  29. int n,m;
  30. vector<int> adj[maxn];
  31. int par[maxn];
  32. int num[maxn],low[maxn];
  33. int dfsTime;
  34. int cut,bridge;
  35. bool dd[maxn];
  36.  
  37. void dfs(int u) {
  38.     if(dd[u]) return;
  39.  
  40.     dd[u] = 1;
  41.     num[u] = ++dfsTime;
  42.  
  43.     int childs = 0;
  44.     bool isCut = 0;
  45.  
  46.     for(int v : adj[u]) {
  47.         if(dd[v]) {
  48.             if(v!=par[u]) low[u] = min(low[u],num[v]);
  49.             continue;
  50.         }
  51.  
  52.         ++childs;
  53.  
  54.         par[v]=u;
  55.         dfs(v);
  56.  
  57.         low[u] = min(low[u],low[v]);
  58.  
  59.         isCut |= (low[v]>=num[u]) && (par[u] || childs>=2) ;
  60.         bridge+=(low[v]>=num[v]);
  61.     }
  62.  
  63.     cut+=isCut;
  64. }
  65. void enter(){
  66.     cin>>n>>m;
  67.  
  68.     int u,v;
  69.  
  70.     forinc(i,1,m) {
  71.         cin>>u>>v;
  72.         adj[u].push_back(v);
  73.         adj[v].push_back(u);
  74.     }
  75. }
  76.  
  77. void solve(){
  78.     fill(low+1,low+n+1,oo);
  79.  
  80.     forinc(i,1,n) dfs(i);
  81.  
  82.     cout<<cut<<" "<<bridge;
  83. }
  84.  
  85. int32_t main()
  86. {
  87.     checkfile(tag);
  88.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  89.  
  90.     enter();
  91.     solve();
  92.  
  93.     return 0;
  94. }
  95.  
Success #stdin #stdout 0.01s 5584KB
comments (?)
stdin
copy 
10 12
1 10
10 2
10 3
2 4
4 5
5 2
3 6
6 7
7 3
7 8
8 9
9 7
stdout
copy 
4 3
https://ideone.com/Xyhqay
language:
C++14 (gcc 8.3)
created:
3 years 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!