fork download
copy 
  1. #include<cstdio>
  2. #include<vector>
  3. using namespace std;
  4.  
  5. const int N = 10005;
  6. int n, m, cut, bridge, t, d[N], low[N];
  7. vector<vector<int> > g;
  8.  
  9. void enter() {
  10. 	scanf("%d%d",&n,&m); g.resize(n);
  11. 	for(int i = 0; i < m; ++i) {
  12. 		int u, v; scanf("%d%d",&u,&v);
  13. 		g[--u].push_back(--v);
  14. 		g[v].push_back(u);
  15. 	}
  16. }
  17.  
  18. void dfs(int u, int p) {
  19. 	low[u] = d[u] = ++t; int iscut = 0, nchild = 0;
  20. 	for(vector<int>::iterator v = g[u].begin(); v != g[u].end(); ++v) 
  21. 		if(d[*v] == 0) {
  22. 			++nchild; dfs(*v, u); low[u] = min(low[u], low[*v]);
  23. 			if(low[*v] >= d[u] && p != -1 || nchild == 2 && p == -1) iscut = 1;
  24. 			if(low[*v] >= d[*v]) ++bridge;
  25. 		} else if(*v != p) low[u] = min(low[u], d[*v]);
  26. 	cut += iscut;
  27. }
  28.  
  29. void solve() {
  30. 	for(int u = 0; u < n; ++u) if(d[u] == 0) dfs(u, -1);
  31. 	printf("%d %d\n", cut, bridge);
  32. }
  33.  
  34. int main() {
  35. 	enter();
  36. 	solve();
  37. 	return 0;
  38. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0 0
https://ideone.com/2v6GFy
language:
C++ (gcc 8.3)
created:
10 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!