fork download
copy 
  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <deque>
  4. #include <vector>
  5.  
  6. constexpr int MAXN = 1004;
  7.  
  8. bool D[MAXN][MAXN];
  9. std::vector<int> E[MAXN];
  10.  
  11. int H[MAXN];
  12. bool visited[MAXN];
  13.  
  14. int main() {
  15. 	int N, M, S;
  16.  
  17. 	scanf("%d%d%d", &N, &M, &S);
  18. 	for (int i = 0; i < M; ++i) {
  19. 		int x, y;
  20. 		scanf("%d%d", &x, &y);
  21. 		D[x][y] = D[y][x] = true;
  22. 	}
  23.  
  24. 	for (int i = 1; i <= N; ++i) {
  25. 		for (int j = 1; j <= N; ++j) {
  26. 			if (D[i][j]) E[i].push_back(j);
  27. 		}
  28. 	}
  29.  
  30. 	// DFS
  31. 	{
  32. 		std::vector<int> V;
  33. 		V.push_back(S);
  34. 		do {
  35. 			const int now = V.back();
  36. 			int &np = H[now];
  37. 			if (!visited[now]) {
  38. 				printf("%d ", now);
  39. 				visited[now] = true;
  40. 			}
  41. 			while (np < (int)E[now].size() && visited[E[now][np]]) ++np;
  42. 			if (np == (int)E[now].size()) V.pop_back();
  43. 			else V.push_back(E[now][np++]);
  44. 		} while (V.size());
  45. 	}
  46.  
  47. 	puts("");
  48. 	std::fill(visited, &visited[N + 1], false);
  49.  
  50. 	// BFS
  51. 	{
  52. 		std::deque<int> Q;
  53. 		Q.push_back(S);
  54. 		visited[S] = true;
  55. 		do {
  56. 			const int now = Q.front();
  57. 			Q.pop_front();
  58. 			printf("%d ", now);
  59.  
  60. 			for (const int &e: E[now]) {
  61. 				if (visited[e]) continue;
  62. 				visited[e] = true;
  63. 				Q.push_back(e);
  64. 			}
  65. 		} while (Q.size());
  66. 	}
  67. }
  68.  
Success #stdin #stdout 0s 4436KB
comments (?)
stdin
copy 
4 5 1
1 2
1 3
1 4
2 4
3 4
stdout
copy 
1 2 4 3 
1 2 3 4
https://ideone.com/juabYc
BOJ 1260
language:
C++14 (gcc 8.3)
created:
8 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!