fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. const int MAX = 1001;
  5.  
  6. class Staque {
  7. private:
  8. 	int staque[MAX] = {}, top = 1, front = 1;
  9. public:
  10. 	bool empty()
  11. 	{
  12. 		if (top == front)
  13. 			return true;
  14. 		else
  15. 			return false;
  16. 	}
  17. 	bool full()
  18. 	{
  19. 		if ((top + 1) % MAX == front)
  20. 			return true;
  21. 		else
  22. 			return false;
  23. 	}
  24. 	void push(int a)
  25. 	{
  26. 		if (full()) return;
  27. 		if (top == 0)
  28. 			++top;
  29. 		staque[(top++)%MAX] = a;
  30. 	}
  31. 	int pop()
  32. 	{
  33. 		if (empty())
  34. 			return 0;
  35. 		return staque[(--top)%MAX];
  36. 	}
  37. 	int deStq()
  38. 	{
  39. 		if (empty())
  40. 			return 0;
  41. 		return staque[(front++)%MAX];
  42. 	}
  43. };
  44.  
  45. class Graph
  46. {
  47. private:
  48. 	std::vector<int> vertex[MAX];
  49. public:
  50. 	void linkVertex(int a, int b) 
  51. 	{
  52. 		int left = 0, right = vertex[a].size() - 1;
  53. 		while (right >= left) {
  54. 			if (b > vertex[a].at((left + right) / 2))
  55. 				left = (left + right) / 2 + 1;
  56. 			else if (b < vertex[a].at((left + right) / 2))
  57. 				right = (left + right) / 2 - 1;
  58. 			else
  59. 				return;
  60. 		}
  61. 		vertex[a].insert(vertex[a].begin() + left, b);
  62. 	}
  63. 	void insertEdge(int a, int b)
  64. 	{
  65. 		if (a == b)
  66. 			return;
  67. 		linkVertex(a, b);
  68. 		linkVertex(b, a);
  69. 	}
  70. 	void DFS(int v)
  71. 	{
  72. 		Staque staque;
  73. 		int visited[MAX] = {}, w;
  74. 		visited[v] = 1;
  75. 		printf("%d ", v);
  76. 		staque.push(v);
  77. 		while (!staque.empty()) {
  78. 			w = 0;
  79. 			while (w < vertex[v].size() && visited[vertex[v].at(w)] == 1) w++;
  80. 			if (w < vertex[v].size()) {
  81. 				w = vertex[v].at(w);
  82. 				visited[w] = 1;
  83. 				printf("%d ", w);
  84. 				staque.push(w);
  85. 				v = w;
  86. 			}
  87. 			else v = staque.pop();
  88. 		}
  89. 	}
  90. 	void BFS(int v)
  91. 	{
  92. 		Staque staque;
  93. 		int visited[MAX] = {}, temp;
  94. 		visited[v] = 1;
  95. 		printf("%d ", v);
  96. 		staque.push(v);
  97. 		while (!staque.empty()) {
  98. 			v = staque.deStq();
  99. 			for (int w = 0; w < vertex[v].size(); w++) {
  100. 				temp = vertex[v].at(w);
  101. 				if (visited[temp] == 0) {
  102. 					visited[temp] = 1;
  103. 					printf("%d ", temp);
  104. 					staque.push(temp);
  105. 				}
  106. 			}
  107. 		}
  108. 	}
  109. };
  110.  
  111. int main(void)
  112. {
  113. 	Graph graph;
  114. 	int n, m, v, v1, v2;
  115.  
  116. 	scanf("%d %d %d", &n, &m, &v);
  117. 	for (int i = 0; i < m; i++) {
  118. 		scanf("%d %d", &v1, &v2);
  119. 		graph.insertEdge(v1, v2);
  120. 	}
  121. 	graph.DFS(v);
  122. 	printf("\n");
  123. 	graph.BFS(v);
  124. }
  125. /*
  126. Input example
  127. 7 6 1
  128. 1 4
  129. 1 3
  130. 1 2
  131. 4 6
  132. 4 5
  133. 2 7
  134.  
  135. Output example
  136. 1 2 7 3 4 5 6
  137. 1 2 3 4 7 5 6
  138. */
Success #stdin #stdout 0s 4348KB
comments (?)
stdin
copy 
7 6 1
1 4
1 3
1 2
4 6
4 5
2 7
stdout
copy 
1 2 7 
1 2 3 4 7 5 6
https://ideone.com/DTDBPE
language:
C++14 (gcc 8.3)
created:
8 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!