题目

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

输入格式：

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

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

输出格式：

输出满足要求的字符串。

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

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

分析

任意俩字母的相邻关系可表示为一条路径，所以在相邻字母间连边，跑字典序最小欧拉回路即可。注意大写字母ASCII码比小写字母小！

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<algorithm>

#include<cctype>

#include<cmath>

#include<cstdlib>

#include<ctime>

#include<queue>

#include<vector>

#include<set>

#include<map>

#include<stack>

using namespace std;

int n,m,minn=1000000007;

int g[1100][1100],du[11000],ans[110000],cnt;

void go(int x){

      int i,j,k;

      for(i=minn;i<=n;i++)

         if(g[x][i]){

             g[x][i]--,g[i][x]--;

             go(i);

         }

      ans[++cnt]=x;

}

int main(){

      int i,j,k,x,y;

      string s;

      cin>>m;

      for(i=1;i<=m;i++){

           cin>>s;

           x=s[0]-'A';

           y=s[1]-'A';

           g[x][y]++,g[y][x]++;

           du[x]++,du[y]++;

           n=max(n,max(x,y));

           minn=min(minn,min(x,y));

      }

      int st=minn;

      int sum=0,chg=0;

      for(i=minn;i<=n;i++)

         if(du[i]&1){

             sum++;

             if(!chg){

             st=i;

             chg=1;

            }

         }

      if(sum!=0&&sum!=2){

        puts("No Solution");

        return 0;

      }

      go(st);

      for(i=cnt;i>0;i--){

         char c=ans[i]+'A';

         cout<<c;

      }

      return 0;

}