fork download
copy 
  1. //#include<iostream>
  2. //#include<algorithm>
  3. //#include<vector>
  4. #include<bits/stdc++.h>
  5. using namespace std;
  6. int a[100][100], n;
  7. stack<int> st;
  8. vector<int> ce;
  9.  
  10. bool lienThong() {
  11. 	stack<int> dinh;
  12. 	int vs[100];
  13. 	memset(vs, 0, sizeof(vs));
  14. 	dinh.push(1);
  15. 	while (!dinh.empty()) {
  16. 		int v = dinh.top();
  17. 		vs[v] = 1;
  18. 		dinh.pop();
  19. 		for (int i = 1; i <= n; i++) {
  20. 			if (a[v][i] && vs[i] == 0) {
  21. 				dinh.push(v);
  22. 				dinh.push(i);
  23. 				break;
  24. 			}
  25. 		}
  26. 	}
  27. 	for (int i = 1; i <= n; i++) {
  28. 		if (vs[i] == 0) return false;
  29. 	}
  30. 	return true;
  31. }
  32.  
  33. void eulerCycleVoHuong(int start) {
  34. 	st.push(start);
  35. 	while (!st.empty()) {
  36. 		int u = st.top();
  37. 		bool check = false;
  38. 		for (int i = 1; i <= n; i++) {
  39. 			if (a[u][i]) {
  40. 				check = true;
  41. 				st.push(i);
  42. 				a[u][i] = 0; a[i][u] = 0;
  43. 				break;
  44. 			}
  45. 		}
  46. 		if (!check) {
  47. 			st.pop();
  48. 			ce.push_back(u);
  49. 		}
  50. 	}
  51. }
  52.  
  53.  
  54. void eulerCycleCoHuong(int start) {
  55. 	st.push(start);
  56. 	while (!st.empty()) {
  57. 		int u = st.top();
  58. 		bool check = false;
  59. 		for (int i = 1; i <= n; i++) {
  60. 			if (a[u][i]) {
  61. 				check = true;
  62. 				st.push(i);
  63. 				a[u][i] = 0;
  64. 				break;
  65. 			}
  66. 		}
  67. 		if (!check) {
  68. 			st.pop();
  69. 			ce.push_back(u);
  70. 		}
  71. 	}
  72. }
  73.  
  74. int main() {
  75. 	cout << "So dinh: ";
  76. 	cin >> n;
  77. 	// Khoi tao ma tran ke
  78. 	cout << "Nhap ma tran:\n";
  79. 	for (int i = 1; i <= n; i++) {
  80. 		for (int j = 1; j <= n; j++) {
  81. 			cin >> a[i][j];
  82. 		}
  83. 	}
  84.  
  85. 	int start;
  86. 	cout << "Bat dau tu dinh: ";
  87. 	cin >> start;
  88.  
  89. 	// uncomment de test thuat toan
  90.  
  91. 	eulerCycleCoHuong(start);
  92. //	eulerCycleVoHuong(start);
  93. 	for (int i = ce.size()-1; i >= 0; i--) {
  94. 		cout << ce[i] << " ";
  95. 	}
  96.  
  97.  
  98.  
  99.  
  100. }
  101.  
  102. /**
  103. Test:
  104.  
  105. vo huong:
  106. (0, 2) (0, 5) (1, 3) (1, 4) (1, 5) (1, 6) (2, 3) (2, 5) (2, 6) (3, 4) (3, 6) (5, 6)
  107.  
  108. 7
  109. 0	0	1	0	0	1	0
  110. 0	0	0	1	1	1	1
  111. 1	0	0	1	0	1	1
  112. 0	1	1	0	1	0	1
  113. 0	1	0	1	0	0	0
  114. 1	1	1	0	0	0	1
  115. 0	1	1	1	0	1	0
  116.  
  117.  
  118. co huong:
  119. 13
  120. 0 1 0 0 0 0 0 0 0 0 0 0 0 
  121. 0 0 1 0 1 0 0 0 0 0 0 0 0 
  122. 0 0 0 1 0 0 0 0 0 0 1 0 0 
  123. 0 0 0 0 0 0 1 0 0 0 1 0 0 
  124. 0 0 1 0 0 1 0 0 0 0 0 0 0 
  125. 1 1 0 0 0 0 0 0 0 0 0 0 0 
  126. 0 0 0 0 1 1 0 0 0 0 0 0 0 
  127. 0 0 0 1 0 0 1 0 0 0 0 0 0 
  128. 0 0 0 0 0 0 0 1 0 1 0 0 0 
  129. 0 0 0 0 0 0 0 1 0 0 0 1 0 
  130. 0 0 0 0 0 0 0 0 0 1 0 1 0 
  131. 0 0 0 0 0 0 0 0 1 0 0 0 1 
  132. 0 0 0 0 0 0 0 0 1 0 0 0 0
  133.  
  134.  
  135.  
  136.  
  137.  
  138.  
  139. **/
Success #stdin #stdout 0.01s 5312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
So dinh: Nhap ma tran:
Bat dau tu dinh: 5255
https://ideone.com/33kM1P
language:
C++ (gcc 8.3)
created:
7 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!