[欧拉回路]无序字母对

无序字母对

题目描述

给定n个各不相同的无序字母对（区分大小写，无序即字母对中的两个字母可以位置颠倒）。请构造一个有n+1个字母的字符串使得每个字母对都在这个字符串中出现。

输入

第一行输入一个正整数n。

以下n行每行两个字母，表示这两个字母需要相邻。

输出

输出满足要求的字符串。

如果没有满足要求的字符串，请输出“No Solution”。

如果有多种方案，请输出前面的字母的ASCII编码尽可能小的（字典序最小）的方案

样例输入

4
aZ
tZ
Xt
aX

样例输出

XaZtX

提示

【数据规模与约定】

n<=1326

代码：

#include<cstdio>
#define H 0x6ffffff
int n, c = 0, map[60][60], d[60], ans[2000], s = H, ss = H, x, y, v, t = 0;
char z[3];

int turn(char c){
    return c - 'A' + 1;
}

char nrut(int a){
    return a + 'A' - 1;
}

void dfs(int i) { 
    for (int j = 1; j <= v; j++) {
          if(map[i][j]>0){
            map[i][j]--;
            map[j][i]--;
            dfs(j);
          }
    }
    ans[++c] = i;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++){
          scanf("%s", z + 1);
          x = turn(z[1]);
        y = turn(z[2]);
          map[x][y]++;
          map[y][x]++;
          d[x]++;
        d[y]++;
          if (x > v) {
            v = x;
        }
          if (y > v) {
            v = y;
        }
    }
    for (int i = 1; i <= v; i++) {
          if(d[i] % 2 == 1) {
            if(s == H) {
                s = i;
            }
            t++;
          }
          if (d[i] > 0 && ss == H) {
            ss = i;
        }
    }
    if (t != 0 && t != 2) {
          printf("No Solution");
          return 0;
    }
    if (s == H) {
        dfs(ss);
    }
    else {
        dfs(s);
    }
    if (c - 1 != n) {
        printf("No Solution");
    }
    else {
          for (int i = c; i >= 1; i--) {
            printf("%c", nrut(ans[i]));
        }
    }
    return 0;
}