fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. struct Node
  4. {
  5. 	int v;
  6. 	int id;
  7. };
  8. int n,m;
  9. vector<vector<Node>> inp;
  10. vector<int> low, num;
  11. vector<bool> joint;
  12. int times = 0;
  13. int bridge = 0;
  14.  
  15.  
  16.  
  17. void dfs(int u, int par)
  18. {
  19. 	low[u] = num[u] = ++times;
  20. 	int child = 0;
  21. 	for(Node v: inp[u])
  22. 	{
  23. 		int x = v.v;
  24. 		int id = v.id;
  25. 		if(id == par) continue;
  26. 		if(num[x] == 0)
  27. 		{
  28. 			dfs(x, id);
  29. 			child++;
  30. 			low[u] = min(low[u], low[x]);
  31. 			if(low[x] == num[x]) bridge++;
  32. 			if(par == -1)
  33. 			{
  34. 				if(child > 1) joint[u] = true;
  35. 			}
  36. 			else if(low[x] >= num[u]) joint[u] = true;
  37. 		}
  38. 		else low[u] = min(low[u], num[x]);
  39. 	}
  40. }
  41. int main()
  42. {
  43. 	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  44. 	cin >> n >>m;
  45. 	inp.resize(n+1);
  46. 	low.resize(n+1);
  47. 	num.resize(n+1);
  48. 	joint.resize(n+1);
  49. 	for(int  i =1; i<=m; i++) 
  50. 	{
  51. 		int a,b; cin >> a >> b;
  52. 		inp[a].push_back({b, i});
  53. 		inp[b].push_back({a, i});
  54. 	}
  55.  
  56. 	for(int i =1; i<=n; i++) if(num[i] == 0) dfs(i, -1);
  57.  
  58. 	int khop =0;
  59. 	for(int i =1; i<=n; i++) khop += joint[i];
  60.  
  61. 	cout << khop << " " << bridge;
  62.  
  63.  
  64.  
  65. 	return 0;
  66. }
Success #stdin #stdout 0s 5332KB
comments (?)
stdin
copy 
9 6
3 6
6 3
4 9
1 6
3 6
5 4
stdout
copy 
2 3
https://ideone.com/2n2Kd3
language:
C++14 (gcc 8.3)
created:
16 hours 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!