fork(2) download
copy 
  1. //============================================================================
  2. // Name        : testowy.cpp
  3. // Author      : kkafara
  4. // Version     :
  5. // Copyright   : Your copyright notice
  6. // Description : SPOJ: Searching the graphs
  7. //============================================================================
  8.  
  9. #include <iostream>
  10. #include <vector>
  11. #include <queue>
  12.  
  13. using namespace std;
  14.  
  15. struct Pair
  16. {
  17. 	int vertex, query_type;
  18. };
  19.  
  20. void dfs(vector<int>G[], bool visited[], int current_vertex)
  21. {
  22. 	visited[current_vertex] = true;
  23.  
  24. 	cout << current_vertex << " ";
  25.  
  26. 	for (vector<int>::iterator i = G[current_vertex].begin(); i != G[current_vertex].end(); ++i)
  27. 	{
  28. 		if(visited[*i] == false) dfs(G, visited, *i);
  29. 	}
  30. }
  31.  
  32. void bfs(vector<int>G[], bool visited[], int current_vertex, queue<int> * vertices_to_process)
  33. {
  34. 	(*vertices_to_process).push(current_vertex);
  35. 	visited[current_vertex] = true;
  36. 	while (!((*vertices_to_process).empty()))
  37. 	{
  38. 		current_vertex = (*vertices_to_process).front();
  39. 		(*vertices_to_process).pop();
  40.  
  41. 		cout << current_vertex << " ";
  42.  
  43. 		for (vector<int>::iterator i = G[current_vertex].begin(); i != G[current_vertex].end(); ++i)
  44. 		{
  45. 			if (visited[*i] == false)
  46. 			{
  47. 				(*vertices_to_process).push(*i);
  48. 				visited[*i] = true;
  49. 			}
  50. 		}
  51.  
  52. 	}
  53.  
  54. }
  55.  
  56. void reset_visited_array(bool visited[], int numb_of_vertices)
  57. {
  58. 	for (int i = 1; i <= numb_of_vertices; ++i)
  59. 		visited[i] = false;
  60. }
  61.  
  62. int main()
  63. {
  64. 	int numb_of_graphs, numb_of_vertices, numb_of_adj, current_vertex, adjacent_vertex;
  65. 	Pair query;
  66.  
  67. 	ios_base::sync_with_stdio(false);
  68.  
  69. 	cin >> numb_of_graphs;
  70.  
  71. 	for (int i = 0; i < numb_of_graphs; ++i)
  72. 	{
  73. 		cin >> numb_of_vertices;
  74. 		vector<int> * graph = new vector<int>[numb_of_vertices + 1];
  75. 		bool * visited = new bool[numb_of_vertices + 1];
  76.  
  77. 		for (int j = 1; j <= numb_of_vertices; ++j)
  78. 		{
  79. 			visited[j] = false;
  80. 			cin >> current_vertex >> numb_of_adj;
  81.  
  82. 			if (numb_of_adj != 0)
  83. 			{
  84. 				for (int k = 0; k < numb_of_adj; ++k)
  85. 				{
  86. 					cin >> adjacent_vertex;
  87. 					graph[j].push_back(adjacent_vertex);
  88. 				}
  89. 			}
  90. 		}
  91.  
  92. 		cout << "graph " << i + 1 << endl;
  93.  
  94. 		for (int j = 0; j < numb_of_vertices; ++j)
  95. 		{
  96. 			cin >> query.vertex >> query.query_type;
  97.  
  98. 			if (query.vertex == 0 && query.query_type == 0)
  99. 				break;
  100.  
  101. 			else if (query.query_type == 0)
  102. 			{
  103. 				dfs(graph, visited, query.vertex);
  104. 				cout << endl;
  105. 			}
  106.  
  107. 			else
  108. 			{
  109. 				queue<int> vertices_to_process;
  110. 				bfs(graph, visited, query.vertex, &vertices_to_process);
  111. 				cout << endl;
  112. 			}
  113.  
  114. 			reset_visited_array(visited, numb_of_vertices);
  115. 		}
  116.  
  117. 		delete[] graph;
  118. 		delete[] visited;
  119. 	}
  120.  
  121. 	return 0;
  122. }
  123.  
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
3
6
1 2 3 4
2 2 3 6
3 2 1 2
4 1 1
5 0
6 1 2
5 1
1 0
1 0
0 0
10
1 6 3 5 6 7 8 9
2 1 9
3 2 1 5
4 5 6 7 8 9 10
5 4 1 3 7 8
6 3 1 4 7
7 5 1 4 5 6 8
8 5 1 4 5 7 10
9 3 1 2 4
10 2 4 8
7 1
1 0
2 1
4 1
7 1
0 0
2
1 0
2 0
1 1
0 0
stdout
copy 
graph 1
5 
1 3 2 6 4 
1 3 2 6 4 
graph 2
7 1 4 5 6 8 3 9 10 2 
1 3 5 7 4 6 8 10 9 2 
2 9 1 4 3 5 6 7 8 10 
4 6 7 8 9 10 1 5 2 3 
7 1 4 5 6 8 3 9 10 2 
graph 3
1
https://ideone.com/6rCkIG
SPOJ: Searching the graphs
Dostaje SIGSEGV (gdzieś wyjeżdża pozakomórki tablicy najprawdopodobniej)
language:
C++ 4.3.2 (gcc-4.3.2)
created:
6 years ago
visibility:
secret

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!