fork download
copy 
  1. #include<iostream>
  2. #include<algorithm>
  3. #include<vector>
  4. #include<cstring>
  5. #include<queue>
  6.  
  7. using namespace std;
  8. int a[100][100], vs[100], n, start;
  9.  
  10. struct Edge{
  11.   int u;
  12.   int v;
  13. };
  14. vector<Edge> T;
  15.  
  16. void TreeDFS(int u) {
  17. 	vs[u] = 1;
  18. 	for (int i = 1; i <= n; i++) {
  19. 		if (vs[i] == 0 && a[u][i] == 1) {
  20. 			Edge e;
  21. 			if (u < i) {
  22. 				e.u = u; e.v = i;
  23. 			} else {
  24. 				e.u = i; e.v = u;
  25. 			}
  26. 			T.push_back(e);
  27. 			TreeDFS(i);
  28. 		}
  29. 	}
  30. }
  31.  
  32. void TreeBFS(int start) {
  33. 	queue<int> q;
  34. 	vs[start] = 1;
  35. 	q.push(start);
  36. 	while (!q.empty()) {
  37. 		int u = q.front();
  38. 		for (int i = 1; i <= n; i++) {
  39. 			if (a[u][i] == 1 && vs[i] == 0) {
  40. 				vs[i] = 1;
  41. 				Edge e;
  42. 				if (u < i) {
  43. 					e.u = u; e.v = i;
  44. 				} else {
  45. 					e.u = i; e.v = u;
  46. 				}
  47. 				T.push_back(e);
  48. 				q.push(i);
  49. 			}
  50. 		}
  51. 		q.pop();
  52. 	}
  53. }
  54.  
  55. int main() {
  56. 	cout << "So dinh: ";
  57.     cin >> n;
  58.     // Khoi tao ma tran ke
  59.     cout << "Nhap ma tran:\n";
  60.     memset(vs, 0, 100);
  61.     for (int i = 1; i <= n; i++) {
  62.         for (int j = 1; j <= n; j++) {
  63.             cin >> a[i][j];
  64.         }
  65.     }
  66.     cout << "Thuc hien tim cay khung tu dinh: ";
  67.     int start;
  68.     cin >> start;
  69.     // TreeDFS(start);
  70.     TreeBFS(start);
  71.     for (int i = 0; i < T.size(); i++) {
  72.     	cout << T[i].u << " " << T[i].v << "\n";
  73. 	}
  74.  
  75. }
  76.  
  77.  
  78. /*
  79. Test
  80. 6
  81. 0 1 1 0 0 0
  82. 1 0 0 1 1 0
  83. 1 0 0 1 0 0
  84. 0 1 1 0 1 1
  85. 0 1 0 1 0 1
  86. 0 0 0 1 1 0
  87.  
  88.  
  89.  
  90. */
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
So dinh: Nhap ma tran:
Thuc hien tim cay khung tu dinh:
https://ideone.com/BtSed9
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!