fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <map>
  4. using namespace std;
  5.  
  6. int v = 8; // number of vertices
  7. vector <vector<int>> adjecancy(v + 1); // adjecncy list of the graph
  8.  
  9. void addEdge(int x,int y) //add edge to the graph
  10. {
  11. 	adjecancy[x].push_back(y);
  12. 	//adjecancy[y].push_back(x);
  13. }
  14.  
  15. void showAdjecancyList(vector <vector<int>> adjecancy)
  16. {
  17. 	for (int i = 1; i < v+1; i++){
  18. 		cout << i << " : ";
  19. 		for (int j = 0; j < adjecancy[i].size(); j++) {
  20. 			cout << adjecancy[i][j] << " ";
  21. 		}
  22. 		cout << endl;
  23. 	}
  24. }
  25.  
  26. int t = 0;
  27. vector <int> arrival(v + 1);
  28. vector <int> departure(v + 1);
  29. map <pair<int, int>, string> edgeType;
  30.  
  31. void edgesTypeArrDepTime(int v)
  32. {
  33. 	arrival[v] = ++t;
  34.  
  35. 	for (int i : adjecancy[v])
  36. 	{
  37. 		if (arrival[i] == 0) //Not visited yet
  38. 		{
  39. 			edgeType[{v, i}] = "tree";
  40. 			edgesTypeArrDepTime(i);
  41. 		}
  42. 		else if (arrival[i] <= arrival[v])
  43. 		{
  44. 			if (departure[i] == 0) //still in recursion stack
  45. 				edgeType[{v, i}] = "back";
  46. 			else
  47. 				edgeType[{v, i}] = "cross";
  48. 		}
  49. 		else
  50. 			edgeType[{v, i}] = "forward";	
  51. 	}
  52.  
  53. 	departure[v] = ++t;
  54. }
  55.  
  56. void showEdgesType(vector <vector<int>> adjecancy)
  57. {
  58. 	for (int i = 1; i < v + 1; i++) {
  59. 		for (int j = 0; j < adjecancy[i].size(); j++) {
  60. 			cout << i << " -> " << adjecancy[i][j] << " ( " << edgeType[{i, adjecancy[i][j]}] << " )\n";
  61. 		}
  62. 	}
  63. }
  64.  
  65. int main()
  66. {
  67. 	ios::sync_with_stdio(false);
  68. 	cin.tie(0); cout.tie(0);
  69.  
  70. 	int n;
  71. 	cin >> n;
  72. 	int x, y;
  73. 	map <int, int> parent;
  74. 	while (n--)
  75. 	{
  76. 		cin >> x >> y;
  77. 		addEdge(x, y);
  78. 		parent[y] = x;
  79. 	}
  80.  
  81. 	edgesTypeArrDepTime(1);
  82.  
  83. 	vector <int> path;
  84.  
  85. 	for (int i = 1; i < v + 1; i++) 
  86. 	{
  87. 		for (int j = 0; j < adjecancy[i].size(); j++) 
  88. 		{
  89. 			if (edgeType[{i, adjecancy[i][j]}] == "back")
  90. 			{
  91. 				path.push_back(adjecancy[i][j]);
  92. 				path.push_back(i);
  93. 				int x = i;
  94. 				while (x != adjecancy[i][j])
  95. 				{
  96. 					path.push_back(parent[x]);
  97. 					x = parent[x];
  98. 				}
  99.  
  100. 				for (int k = path.size() - 1; k >= 0; k--)
  101. 					cout << path[k] << " ";
  102. 				cout << endl;
  103. 				path.clear();
  104. 			}
  105. 		}
  106. 	}
  107. }
Success #stdin #stdout 0s 4556KB
comments (?)
stdin
copy 
9
6 8
1 1
1 2
2 3
3 4
4 2
2 5
5 6
6 5
stdout
copy 
1 1 
2 3 4 2 
5 6 5
https://ideone.com/xOyU65
language:
C++ 4.3.2 (gcc-4.3.2)
created:
5 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!