fork(1) download
copy 
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. const int MAX_N = 300005;
  7.  
  8. int bridgec;
  9. vector<int> adj [MAX_N];
  10.  
  11. int lvl [MAX_N];
  12. int dp [MAX_N];
  13.  
  14. void visit (int vertex) {
  15. 	dp[vertex] = 0;
  16. 	vector<int> temp;
  17. 	int par = 0;
  18. 	int child = 0;
  19. 	for (int nxt : adj[vertex])
  20. 	{
  21. 		if (lvl[nxt] == 0)
  22. 		{	/* edge to child */
  23. 			child++;
  24. 			if (!temp.empty())
  25. 			{
  26. 				temp[temp.size() - 1] -= par;
  27. 				par = 0;
  28. 			}
  29. 			lvl[nxt] = lvl[vertex] + 1;
  30. 			visit(nxt);
  31. 			dp[vertex] += dp[nxt];
  32. 			temp.push_back(dp[nxt]);
  33. 		}
  34. 		else if (lvl[nxt] < lvl[vertex])
  35. 		{	/* edge upwards */
  36. 			dp[vertex]++;
  37. 		}
  38. 		else if (lvl[nxt] > lvl[vertex])
  39. 		{	/* edge downwards */
  40. 			dp[vertex]--;
  41. 			par++;
  42. 		}
  43.  
  44. 	}
  45. 	/* the parent edge isn't a back-edge, subtract 1 to compensate */
  46. 	dp[vertex]--;
  47.  
  48. 	//Special Cases
  49. 	if (child == 0)
  50. 		return;//leave node
  51. 	if (vertex == 1)
  52. 	{
  53. 		// root node
  54. 		if (child > 1)
  55. 		{
  56. 			cout << "vertex " << vertex << endl;
  57. 			bridgec++;
  58. 		}
  59. 		return;
  60. 	}
  61.  
  62. 	//General Cases
  63. 	temp[temp.size() - 1] -= par;
  64. 	int flag = 0;
  65. 	for (int x : temp)
  66. 	{
  67. 		if (x != 0) continue;
  68. 		else {
  69. 			flag = 1;
  70. 		}
  71. 	}
  72. 	if (flag)
  73. 	{
  74. 		cout << "vertex " << vertex << endl;
  75. 		bridgec++;
  76. 	}
  77. }
  78.  
  79. int main () {
  80. 	/* problem statement: given a connected graph. calculate the number of articulation points. */
  81. 	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  82. #ifndef ONLINE_JUDGE
  83. 	freopen("input.txt", "r", stdin);
  84. 	freopen("output.txt", "w", stdout);
  85. #endif
  86. 	int vertexc, edgec;
  87. 	cin >> vertexc >> edgec;
  88.  
  89. 	for (int i = 0; i < edgec; i++) {
  90. 		int u, v;
  91. 		cin >> u >> v;
  92.  
  93. 		adj[u].push_back(v);
  94. 		adj[v].push_back(u);
  95. 	}
  96.  
  97. 	lvl[1] = 1;
  98. 	visit(1);
  99. 	cout << bridgec << endl;
  100. }
Runtime error #stdin #stdout 0.01s 11616KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/xmRFhS
language:
C++14 (gcc 8.3)
created:
2 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!