传送门

#include <bits/stdc++.h>
using namespace std;

int n;
bool a[53][53],de[53];
char s[5];

int calc(char c){
    if (c>='a' && c<='z') return c-'a'+27;
    else return c-'A'+1;
}
char uncalc(int x){
    if (x>=1 && x<=26) return 'A'+x-1;
    else return 'a'+x-27;
}

stack <int> st;

void dfs(int x){
    for (int i=1;i<=52;++i){
        if (a[x][i]){
            a[x][i]=a[i][x]=0; //无向图不可反复走
            dfs(i);
            //如果要记录边，应在此处
        }
    }
    st.push(x);
}

int main(){
    cin>>n;
    int mt=52;
    for (int i=1;i<=n;++i){
        scanf("%s",s+1);
        int x=calc(s[1]),y=calc(s[2]);
        mt=min(mt,min(x,y));
        a[x][y]=a[y][x]=1;
        de[x]^=1,de[y]^=1;
    }
    vector <int> v;
    for (int i=1;i<=52;++i){
        if (de[i]&1){
            v.push_back(i);
        }
    }
    if (v.size()==0){
        dfs(mt);
    }else if (v.size()==2){
        dfs(v[0]);
    }else{
        puts("No Solution");
        return 0;
    }
    /**
     * 此处没有判图的连通性，一般是要判的，数据比较水
     */
    while (!st.empty()){
        printf("%c",uncalc(st.top()));
        st.pop();
    }
    return 0;
}

/**
 * 欧拉路问题
 * 定义：
 *      欧拉路径：从S-T存在一条路径，使得不重复地便历图中所有的边
 *      欧拉回路：上述定义中S=T的情况
 * 判定：
 *         首先图是连通图
 *         欧拉路径：无向图：有2个或0个点度数为奇；有向图：最多只能有两个点入度不等于出度，而且这两个点其中一个点的入度+1=出度，另一个点的出度+1=入度；
 *         欧拉回路：无向图：没有奇度数的点；有向图：所有顶点的入度等于出度；
 * 查找方案：
 *         如果有特殊点（奇度数；出度=入度+1），从该点开始；否则从任意一点开始
 *         注意路径上点和边的记录要到子节点dfs完后push，最后倒序输出
 */

本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。
本文链接：https://hs-blog.axell.top/archives/%E6%AC%A7%E6%8B%89%E8%B7%AF%E5%BE%84-%E5%9B%9E%E8%B7%AF%E3%80%90luogu-p1341%E3%80%91/