fork download
copy 
  1. // C++ implementation 
  2. #include <bits/stdc++.h> 
  3. using namespace std; 
  4.  
  5. // An utility function to add an edge in an 
  6. // undirected graph. 
  7. void addEdge(vector<int> v[], 
  8. 			int x, 
  9. 			int y) 
  10. { 
  11. 	v[x].push_back(y); 
  12. 	v[y].push_back(x); 
  13. } 
  14.  
  15. // A function to print the path between 
  16. // the given pair of nodes. 
  17. void printPath(vector<int> stack) 
  18. { 
  19. 	int i; 
  20. 	for (i = 0; i < (int)stack.size() - 1; 
  21. 		i++) { 
  22. 		cout << stack[i] << " -> "; 
  23. 	} 
  24. 	cout << stack[i]; 
  25. } 
  26.  
  27. // An utility function to do 
  28. // DFS of graph recursively 
  29. // from a given vertex x. 
  30. void DFS(vector<int> v[], 
  31. 		bool vis[], 
  32. 		int x, 
  33. 		int y, 
  34. 		vector<int> stack) 
  35. { 
  36. 	stack.push_back(x); 
  37. 	if (x == y) { 
  38.  
  39. 		// print the path and return on 
  40. 		// reaching the destination node 
  41. 		printPath(stack); 
  42. 		return; 
  43. 	} 
  44. 	vis[x] = true; 
  45.  
  46. 	// A flag variable to keep track 
  47. 	// if backtracking is taking place 
  48. 	int flag = 0; 
  49. 	if (!v[x].empty()) { 
  50. 		for (int j = 0; j < v[x].size(); j++) { 
  51. 			// if the node is not visited 
  52. 			if (vis[v[x][j]] == false) { 
  53. 				DFS(v, vis, v[x][j], y, stack); 
  54. 				flag = 1; 
  55. 			} 
  56. 		} 
  57. 	} 
  58. 	if (flag == 0) { 
  59.  
  60. 		// If backtracking is taking 
  61. 		// place then pop 
  62. 		stack.pop_back(); 
  63. 	} 
  64. } 
  65.  
  66. // A utility function to initialise 
  67. // visited for the node and call 
  68. // DFS function for a given vertex x. 
  69. void DFSCall(int x, 
  70. 			int y, 
  71. 			vector<int> v[], 
  72. 			int n, 
  73. 			vector<int> stack) 
  74. { 
  75. 	// visited array 
  76. 	bool vis[n + 1]; 
  77.  
  78. 	memset(vis, false, sizeof(vis)); 
  79.  
  80. 	// DFS function call 
  81. 	DFS(v, vis, x, y, stack); 
  82. } 
  83.  
  84. // Driver Code 
  85. int main() 
  86. { 
  87. 	int n = 11; 
  88. 	vector<int> v[n], stack; 
  89.  
  90. 	// Vertex numbers should be from 1 to 9. 
  91. 	addEdge(v, 1, 2); 
  92. 	addEdge(v, 1, 3); 
  93. 	addEdge(v, 3, 4); 
  94. 	addEdge(v, 4, 5); 
  95. 	addEdge(v, 5, 6); 
  96. 	addEdge(v, 2, 7); 
  97. 	addEdge(v, 6, 8); 
  98. 	addEdge(v, 8, 10); 
  99. 	addEdge(v, 7, 9);
  100.  
  101. 	// Function Call 
  102. 	DFSCall(7, 8, v, n, stack); 
  103.  
  104. 	return 0; 
  105. } 
  106.  
Success #stdin #stdout 0s 4452KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
7 -> 2 -> 1 -> 3 -> 4 -> 5 -> 6 -> 8
https://ideone.com/cKH5iw
language:
C++14 (gcc 8.3)
created:
4 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!