Luogu

算法

建图求欧拉路即可。

代码

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

const int MAXN=256;
int G[MAXN][MAXN];
int degree[MAXN];
char ans[MAXN*MAXN];
char tmp[MAXN];
int n;

inline void Hierholzer(int u) {
    for (re int v=0;v<MAXN;v++)
        if (G[u][v]) {
            G[u][v]=G[v][u]=0;
            Hierholzer(v);
        }
    ans[n--]=u;
}

int main() {
    ios::sync_with_stdio(false);
    cin>>n;
    for (re int i=1;i<=n;i++) {
        cin>>tmp;
        G[tmp[0]][tmp[1]]=G[tmp[1]][tmp[0]]=1;
        degree[tmp[0]]++; degree[tmp[1]]++;
    }
    char s=0; int cnt=0;
    for (re int i=0;i<MAXN;i++) {
        if (degree[i]&1) {
            cnt++;
            if (!s) s=i;
        }
    }
    if (!s) {
        for (re int i=0;i<MAXN;i++)
            if (degree[i]) { s=i; break; }
    }
    if (cnt!=0&&cnt!=2) { puts("No Solution"); return 0; }
    Hierholzer(s);
    puts(ans);
    return 0;
}
最后修改:2019 年 09 月 24 日 01 : 01 PM