「题解」无序字母对

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

一 题目

原题链接

描述

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

输入

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

输出

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

---

二 题解

把单个字母看作图上的点，字母的相邻关系（也就是上文中的“字母对”）看作无向边。即对于一个字母对$ab$，将$a$与$b$连无向边。

题目中描述“使得每个字母对都在这个字符串中出现”，即可看作图上的每条边都要被经过。所以得出本题为欧拉路问题，求出字典序最小的欧拉道路（或回路）即可解决问题。

因为一共26个英文字母，算上大小写区分还不到100个，所以本题使用邻接矩阵存图更为方便。直接把char型字符强制转换为int型的ascii码，求解即可。
注意：在涉及类型转换时，需要注重细节的处理。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;

const int CP=1e3+3;
const int CE=CP*CP;

bool g[CP][CP]; //邻接矩阵

int elm[CP]; //所有出现的字符（强转int），也可以理解为图的点集
bool ap[CP]; //一个字符是否已经被记录

int n;

//euler path
int deg[CP]; //节点的度
int list[CP]; //答案数组

bool exm(){
    int sum=0;
    for(int i=1;i<=n;i++)
        if(deg[elm[i]]%2)
            sum++;
    return sum<=2; //仅当奇点个数小于2时有解（这里没有判断图的连通性，下面还需要判断）
}
void dfs(int u)
{
    for(int j=1;j<=elm[0];j++) //从小到大遍历，为了字典序尽量小
    {
        int v=elm[j];
        if(g[u][v])
        {
            g[u][v]=g[v][u]=false; //删边
            dfs(v);     
        }
    }  
    list[++list[0]]=u; //必须在退栈的时候记录，想想为什么
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        char _x,_y;
        cin>>_x>>_y;
        int x=_x,y=_y; //转换成int
        
        g[x][y]=g[y][x]=true; //邻接矩阵
        
        deg[x]++; //记录节点的度
        deg[y]++;
        
        if(!ap[x]) //统计出现的字符
        {
            elm[++elm[0]]=x;
            ap[x]=true;
        }
        if(!ap[y])
        {
            elm[++elm[0]]=y;
            ap[y]=true;
        }
    }
    
    sort(elm+1,elm+elm[0]+1); //排序，为了得到最小字典序
    
    int s=elm[1]; //无奇点从最小的点开始
    for(int i=1;i<=n&&s==elm[1];i++)
        if(deg[elm[i]]%2)
           s=elm[i]; //有奇点从最小的奇点开始
           
    dfs(s);
    if(exm() && list[0]==n+1) //解的长度不为n-1，图一定不联通
        for(int i=list[0];i;i--) //一定倒着输出
        {
            char c=list[i]; //再转换成char型
            cout<<c;
        }
    else
        printf("No Solution");
    
    return 0;    
}