[欧拉路] Luogu – 1341 无序字母对

题目描述

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

 

输入格式

第一行输入一个正整数 $n$ 。
以下 $n$ 行每行两个字母，表示这两个字母需要相邻。

 

输出格式

输出满足要求的字符串。
如果没有满足要求的字符串，请输出“No Solution”。
如果有多种方案，请输出前面的字母的ASCII编码尽可能小的（字典序最小）的方案

 

输入样例#1

4
aZ
tZ
Xt
aX

输出样例#1

XaZtX

数据规模与约定

不同的无序字母对个数有限，$n$ 的规模可以通过计算得到。

本题是一道典型的欧拉路问题，将每个字母看做一个节点，一个约束条件建一条边，如果一个图是欧拉环，那么每个点的度数都是偶数，如果是一条欧拉路径，那么将会有2个点的度数是奇数，否则就不是一条欧拉环/欧拉路径，需要输出Impossible。题目同时要求输出字典序最小的一个字符串，对于欧拉环，从字典序最小的节点开始dfs，对于一个欧拉路径，从两个奇数度数节点中选取字典序小的节点开始进行dfs。

代码

#include
#include
#include
#include
#include
#include
#define LL long long

using namespace std;
const int MAXN = 2000;

int in[MAXN];
int map[MAXN][MAXN];
int line[MAXN];
int cnt,n;

inline int read(char ch){
    if('a' <= ch && ch <= 'z') return ch - 'a' + 27;
    return ch - 'A' + 1;
} 

inline char print(int x){
    if(x<=26)
        return x + 'A' - 1;
    return 'a' + x - 27;
}

inline void addedge(int u,int v){
    in[u] ++;
    in[v] ++;

    map[u][v] = map[v][u] = 1;
} 

inline void dfs(int root){
    for(int i=1;i<=52;i++)
        if(map[root][i]){
            map[root][i] = map[i][root] = 0;
            dfs(i);
        }

    line[++cnt] = root;
}

int main(){
    scanf("%d",&n);
    char ch[10];

    for(int i=1;i<=n;i++){
        scanf("%s",ch);
        addedge(read(ch[0]),read(ch[1])); //建边
    }

    int p = 0x3f3f3f3f;

    for(int i=1;i<=52;i++)
        if(in[i] %2 == 1){
            p = min(p,i); //记录起点
            cnt++; //统计度数为奇数的个数
        }

    if(cnt!=0 && cnt!=2){
        printf("No Solution\n");
        return 0;
    } 

    if(cnt==0)
        for(int i=1;i<=52;i++)
            if(in[i]){
                p = i; //找到字典序最小的节点
                break;
            }

    cnt = 0;
    dfs(p);

    for(int i=cnt;i>=1;i--)
        printf("%c",print(line[i]));
    return 0;
}