Advertisement
Guest User

Untitled

a guest
Mar 1st, 2015
209
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.20 KB | None | 0 0
  1. #include <iostream>
  2. #include <fstream>
  3. #include <cmath>
  4. #include <algorithm>
  5. #include <vector>
  6. #include <set>
  7. #include <map>
  8. #include <stack>
  9. #include <queue>
  10. #include <cstdlib>
  11. #include <cstdio>
  12. #include <string>
  13. #include <cstring>
  14. #include <cassert>
  15. #include <utility>
  16. #include <iomanip>
  17.  
  18. using namespace std;
  19.  
  20. const int MAXN = 5 * 1050;
  21.  
  22. struct edge {
  23. int to;
  24. bool used;
  25. bool bad;
  26. };
  27.  
  28. int n;
  29. char ss[5];
  30. vector <edge> e;
  31. vector <int> g[MAXN];
  32. int in[MAXN], out[MAXN];
  33. vector <int> ans;
  34. int s = -1, t = -1;
  35.  
  36. void dfs(int v) {
  37. for (int i = 0; i < (int) g[v].size(); i++) {
  38. int ind = g[v][i];
  39. int to = e[ind].to;
  40. if (e[ind].used)
  41. continue;
  42. e[ind].used = true;
  43. dfs(e[ind].to);
  44. }
  45. ans.push_back(v);
  46. }
  47.  
  48. int main() {
  49. //assert(freopen("input.txt","r",stdin));
  50. //assert(freopen("output.txt","w",stdout));
  51.  
  52. scanf("%d\n", &n);
  53.  
  54. for (int i = 1; i <= n; i++) {
  55. gets(ss);
  56. int from = (int) ss[0] * 10 + (int) ss[1];
  57. int to = (int) ss[1] * 10 + (int) ss[2];
  58. //cerr << from << " " << to << endl;
  59. edge ed;
  60. ed.to = to;
  61. ed.used = false;
  62. e.push_back(ed);
  63. g[from].push_back( (int) e.size() - 1);
  64. out[from]++; in[to]++;
  65. }
  66.  
  67. for (int i = 0; i < 3000; i++) {
  68. if ((in[i] % 2 == 0) && (out[i] % 2 == 0))
  69. continue;
  70. if (out[i] > in[i]) {
  71. if (s == -1) {
  72. s = i;
  73. }
  74. else {
  75. puts("NO");
  76. return 0;
  77. }
  78. }
  79. if (in[i] > out[i]) {
  80. if (t == -1) {
  81. t = i;
  82. }
  83. else {
  84. puts("NO");
  85. return 0;
  86. }
  87. }
  88. }
  89.  
  90. if (s == -1 || t == -1) {
  91. puts("NO");
  92. return 0;
  93. }
  94.  
  95. edge ed;
  96. ed.to = s;
  97. ed.bad = true;
  98. ed.used = true;
  99. e.push_back(ed);
  100. g[t].push_back( (int) e.size() - 1);
  101.  
  102. dfs(s);
  103.  
  104. puts("YES");
  105.  
  106. int len = (int) ans.size();
  107.  
  108. for (int i = 0; i < len; i++)
  109. cout << ans[i] << " ";
  110. cout << endl;
  111.  
  112. int st = 0;
  113. for (int i = 0; i < len; i++) {
  114. if (i + 1 < len && ans[i] == t && ans[i + 1] == s) {
  115. st = i + 1;
  116. break;
  117. }
  118. }
  119.  
  120. for (int j = 0; j < len - 1; j++) {
  121. int from = ans[(st + j) % len], to = ans[(st + j + 1) % len];
  122. if (j == 0) {
  123. putchar(from / 10);
  124. putchar(from % 10);
  125. }
  126. putchar(to % 10);
  127. }
  128.  
  129. cout << endl;
  130.  
  131. return 0;
  132. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement