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. 		bool visited[MAX] = {};
  74. 		staque.push(v);
  75. 		while (!staque.empty()) {
  76. 			v = staque.pop();
  77.  
  78. 			if(!visited[v]){
  79. 				printf("%d ", v);
  80. 				visited[v] = true;
  81. 			}
  82. 			for(int w : vertex[v])
  83. 				if(!visited[w])
  84. 					staque.push(w);
  85. 			// w = 0;
  86. 			// while (w < vertex[v].size() && visited[vertex[v].at(w)] == 1) w++;
  87. 			// if (w < vertex[v].size()) {
  88. 			// 	w = vertex[v].at(w);
  89. 			// 	visited[w] = 1;
  90. 			// 	printf("%d ", w);
  91. 			// 	staque.push(w);
  92. 			// 	v = w;
  93. 			// }
  94. 			// else v = staque.pop();
  95.  
  96. 		}
  97. 	}
  98. 	void BFS(int v)
  99. 	{
  100. 		Staque staque;
  101. 		int visited[MAX] = {}, temp;
  102. 		visited[v] = 1;
  103. 		printf("%d ", v);
  104. 		staque.push(v);
  105. 		while (!staque.empty()) {
  106. 			v = staque.deStq();
  107. 			for (int w = 0; w < vertex[v].size(); w++) {
  108. 				temp = vertex[v].at(w);
  109. 				if (visited[temp] == 0) {
  110. 					visited[temp] = 1;
  111. 					printf("%d ", temp);
  112. 					staque.push(temp);
  113. 				}
  114. 			}
  115. 		}
  116. 	}
  117. };
  118.  
  119. int main(void)
  120. {
  121. 	Graph graph;
  122. 	int n, m, v, v1, v2;
  123.  
  124. 	scanf("%d %d %d", &n, &m, &v);
  125. 	for (int i = 0; i < m; i++) {
  126. 		scanf("%d %d", &v1, &v2);
  127. 		graph.insertEdge(v1, v2);
  128. 	}
  129. 	graph.DFS(v);
  130. 	printf("\n");
  131. 	graph.BFS(v);
  132. }
  133. /*
  134. Input example
  135. 7 6 1
  136. 1 4
  137. 1 3
  138. 1 2
  139. 4 6
  140. 4 5
  141. 2 7
  142.  
  143. Output example
  144. 1 2 7 3 4 5 6
  145. 1 2 3 4 7 5 6
  146. */
Success #stdin #stdout 0s 4480KB
comments (?)
stdin
copy 
7 6 1
1 4
1 3
1 2
4 6
4 5
2 7
stdout
copy 
1 4 6 5 3 2 7 
1 2 3 4 7 5 6
https://ideone.com/p6zFVL
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!