一笔话问题

大哥博客 

https://blog.csdn.net/c20182030/article/details/52755880

好骚啊

注意  dfs时不能用 vis 不然会少访问；先毁灭图在访问；

例题：

问题描述 

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

输入

输入数据 

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

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

输出

输出数据 

    输出满足要求的字符串。 

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

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

 

样例输入 Copy

4
aZ
tZ
Xt
aX

样例输出 Copy

XaZtX
代码

#include <bits/stdc++.h>
using namespace std;
#define ri register int 
const int M =1005;
struct setbian{
    int net,to;
}bian[M];
int cent ,head[M],du[M],num,kaishi,trmp,vis[M],arr[M][M];
char ans[M];
void add(int a,int b)
{
    bian[++cent].net=head[a],head[a]=cent;
    bian[cent].to=b;
}
void dfs(int k)
{    
    for(ri i=1;i<=150;i++)
      if(arr[k][i]==1)
       {
             arr[i][k]=0;
             arr[k][i]=0;
             dfs(i);
       }
    ans[++trmp]=k;
}
int m;
int main(){
    scanf("%d",&m);
    for(ri i=1;i<=m;i++)
    {  char c;
       int a,b;
        cin>>c;
        a=c;
        cin>>c;
        b=c;
      arr[a][b]=arr[b][a]=1;
       du[a]++,du[b]++;
    }
    for(ri i='A';i<='z';i++)
    {
        if(du[i]%2==0) continue;
        if(du[i]%2==1) 
        {
            num++;
            if(kaishi==0) kaishi=i;
        }
    }
    if(num!=0&&num!=2) 
    printf("No Solution");
    else
    {  if(kaishi==0) 
       {  int i='A';
             while(du[i]==0) i++;
             kaishi=i;
       }
        dfs(kaishi);
        if(trmp<m+1) printf("No Solution");
        else
        for(ri i=trmp;i>=1;i--)
        {
            printf("%c",ans[i]);
        }
    
    }
}