Tranvick

29.2

Jun 1st, 2014
246
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.02 KB | None | 0 0
  1. #include <cstdio>
  2. #include <string>
  3. #include <vector>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. const int MAX_LEN = (int)1e6 + 10;
  9. const int M = 255;
  10. const int N = M + M;
  11.  
  12. struct Edge {
  13.     int to;
  14.     string word;
  15.     Edge(int to, const string &s)
  16.         : to(to), word(s) {
  17.     }
  18.     Edge() {
  19.     }
  20. };
  21.  
  22. vector<Edge> g[N];
  23. vector<string> result;
  24. char buffer[MAX_LEN];
  25. int degIn[N], degOut[N];
  26. bool used[N];
  27.  
  28. void addEdge() {
  29.     Edge e;
  30.     e.word = buffer;
  31.     e.to = e.word.back() + M;
  32.     g[buffer[0] + M].push_back(e);
  33.     ++degIn[e.to];
  34.     ++degOut[buffer[0] + M];
  35. }
  36.  
  37. void input() {
  38.     int m;
  39.     scanf("%d\n", &m);
  40.     for (int i = 0; i < m; ++i) {
  41.         gets(buffer);
  42.         addEdge();
  43.     }
  44. }
  45.  
  46. void dfsCheck(int v) {
  47.     used[v] = true;
  48.     for (size_t i = 0; i < g[v].size(); ++i) {
  49.         if (!used[g[v][i].to]) {
  50.             dfsCheck(g[v][i].to);
  51.         }
  52.     }
  53. }
  54.  
  55. bool checkConnectivity() {
  56.     int c = 0;
  57.     for (int i = 0; i < N; ++i) {
  58.         if (degIn[i] + degOut[i] > 0 && !used[i]) {
  59.             dfsCheck(i);
  60.             ++c;
  61.         }
  62.     }
  63.     return c < 2;
  64. }
  65.  
  66. bool checkDegrees() {
  67.     for (int i = 0; i < N; ++i) {
  68.         if (degIn[i] != degOut[i]) {
  69.             return false;
  70.         }
  71.     }
  72.     return true;
  73. }
  74.  
  75. void dfs(int v, const string &word) {
  76.     while (g[v].size() > 0) {
  77.         Edge e = g[v].back();
  78.         g[v].pop_back();
  79.         dfs(e.to, e.word);
  80.     }
  81.     result.push_back(word);
  82. }
  83.  
  84. void getEulerCicle() {
  85.     for (int i = 0; i < N; ++i) {
  86.         if (degIn[i]) {
  87.             dfs(i, "");
  88.             break;
  89.         }
  90.     }
  91. }
  92.  
  93. int main() {
  94.     freopen("input.txt", "r", stdin);
  95.     freopen("output.txt", "w", stdout);
  96.     input();
  97.     if (!checkConnectivity() || !checkDegrees()) {
  98.         printf("No");
  99.         return 0;
  100.     }
  101.     puts("Yes");
  102.     getEulerCicle();
  103.     reverse(result.begin(), result.end());
  104.     for (size_t i = 1; i < result.size(); ++i) {
  105.         puts(result[i].c_str());
  106.     }
  107.     return 0;
  108. }
Advertisement
Add Comment
Please, Sign In to add comment