本文共 1245 字，大约阅读时间需要 4 分钟。

题目描述

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

输入输出格式

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

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

输出格式：

输出满足要求的字符串。

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

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

输入输出样例

输入样例#1：

输出样例#1：

说明

【数据规模与约定】

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

这只是一道waterful的题，（然而，并没有一次A（尴尬）），A..z并不是52个，而是…自己算吧（我才不会告诉你代码里有）

#include
   
    #include
    
     using namespace std;int n,k,s=101,a[101],ans[8001],du[101];bool b[101][101];void dfs(int u){    for(int i=1;i<=58;i++)        if(b[u][i])        {            b[u][i]=b[i][u]=0;            dfs(i);        }    k++;    ans[k]=u;}int main(){    scanf("%d",&n);    for(int i=1;i<=n;i++)    {        char tmp[2];        scanf("%s",tmp);        int x,y;        x=tmp[0]-'A'+1;        y=tmp[1]-'A'+1;        s=min(s,min(x,y));        du[x]++;        du[y]++;        b[x][y]=b[y][x]=1;    }    for(int i=1;i<=58;i++)        if(du[i]%2==1)            a[++a[0]]=i;    if(a[0]==0)    {        dfs(s);        for(int i=k;i>=1;i--)            printf("%c",ans[i]+'A'-1);    }    else if(a[0]==2)    {        dfs(a[1]);        for(int i=k;i>=1;i--)            printf("%c",ans[i]+'A'-1);    }    else        printf("No Solution");    printf("\n");    return 0;}
    
   

转载地址：https://blog.csdn.net/Rlt1296/article/details/51893069 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！