fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. vector<int> graph[1001];
  5. vector<int> cycle_track;
  6.  
  7. int degree[1001] = {0};
  8. bool vis[1001] = {0};
  9. bool mark[1001] = {0};
  10.  
  11. int spanner_sum = 0;
  12.  
  13.  
  14. void process_cycle() {
  15. 	int min_degree_edge = 0;
  16. 	int curr_v = cycle_track[0];
  17. 	int min_degree_edge_v1 = 0, min_degree_edge_v2 = 0;
  18. 	//cout << endl;
  19. 	for (int i = 0; i < cycle_track.size(); i++) {
  20. 		//cout << cycle_track[i] << " ";
  21. 	}
  22. 	//cout << endl;
  23. 	for (int i = 1; i < cycle_track.size(); i++) {
  24. 		mark[curr_v] = true;
  25. 		int next_v = cycle_track[i];
  26. 		int curr_v_degree = degree[curr_v];
  27. 		int next_v_degree = degree[next_v];
  28. 		if (curr_v_degree + next_v_degree > min_degree_edge) {
  29. 			min_degree_edge = curr_v_degree + next_v_degree;
  30. 			min_degree_edge_v1 = curr_v;
  31. 			min_degree_edge_v2 = next_v;
  32. 		}
  33. 		curr_v = next_v;
  34. 	}
  35. 	degree[min_degree_edge_v1]--;
  36. 	degree[min_degree_edge_v2]--;
  37. }
  38.  
  39.  
  40. void find_cycle_dfs(int curr_v, int parent, int cycle_len, int curr_depth, int &e) {
  41. 	//cout << "cv "<<curr_v << ". Cycle len, Curr depth = " << cycle_len << " " << curr_depth << endl;
  42. 	vis[curr_v] = true;
  43. 	cycle_track.push_back(curr_v);
  44. 	//cout << endl;
  45. 	for (int i = 0; i < cycle_track.size(); i++) {
  46. 		//cout << cycle_track[i] << " ";
  47. 	}
  48. 	//cout << endl;
  49. 	for (int adj_v : graph[curr_v]) {
  50. 		if (!mark[adj_v] and adj_v != parent) {
  51. 			if (curr_depth <= cycle_len and !vis[adj_v]) {
  52. 				find_cycle_dfs(adj_v, curr_v, cycle_len, curr_depth + 1, e);
  53. 			} else if (curr_depth == cycle_len + 1 and vis[adj_v]) {
  54. 				//cout << "* " << cycle_len << " " << curr_v <<endl;				
  55. 				spanner_sum += 2* (cycle_len - 1);
  56. 				cycle_track.push_back(adj_v);
  57. 				process_cycle();
  58. 				e--;
  59. 				cycle_track.pop_back();
  60. 			}
  61. 		}
  62. 	}
  63. 	//cout << "end"<<curr_v << endl;
  64. 	vis[curr_v] = false;
  65. 	cycle_track.pop_back();
  66. }
  67.  
  68.  
  69. void dfs_helper(int v, int &e) {
  70. 	int cycle_len = 3;
  71. 	while (e > v - 1) {
  72. 		for (int i = 0; i < v; i++) {
  73. //find_cycle_dfs(int curr_v, int parent, int cycle_len, int curr_depth) {
  74. 			find_cycle_dfs(i, i ,cycle_len, 1, e);
  75. 		}
  76. 		cycle_len++;
  77. 	}
  78. }
  79.  
  80. int main() {
  81. 	int v, e;
  82. 	cin >> v >> e;
  83. 	for (int i = 0; i < e; i++) {
  84. 		int v1, v2;
  85. 		cin >> v1 >> v2;
  86. 		graph[v1].push_back(v2);
  87. 		degree[v1]++;
  88. 		graph[v2].push_back(v1);
  89. 		degree[v2]++;
  90. 	}
  91. 	for(int i = 0; i < 10; i++) {
  92. 		//cout << i << ": ";
  93. 		for(int j: graph[i]) {
  94. 			//cout << j << " ";
  95. 		}	
  96. 		//cout << endl;
  97. 	}
  98. 	dfs_helper(v, e);
  99. 	//cout << spanner_sum << endl;
  100. }
Runtime error #stdin #stdout 0s 16096KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/KDztVn
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!