無秩序アルファベット対洛谷1341オーラ通路/オーラ戻り路

タイトルの説明
n個の異なる無秩序アルファベット対(大文字と小文字を区別し、無秩序、すなわちアルファベット対の2つのアルファベットを位置逆にすることができる)を与えた.各アルファベットペアがこの文字列に現れるようにn+1文字の文字列を作成してください.
ぶんせき
まず、テーマを見て、サンプルを見ると、アルファベットのペアが[b]につながっていなければならないことに気づき、図の遍歴などを思い出します.ちょっとインスピレーションがあれば、オラトは大丈夫だと思います.
それから図を建てるとはっきりします.アルファベットを図の頂点とし、2文字の母の間にアルファベット対が存在する場合、対応するアルファベットの対応する頂点に5方向のエッジが接続されます.テーマは辞書順が最も小さいオラ通路を要求している.
オーラパスの存在は,0個または2個の度数が奇数の頂点のみが存在し,度数が奇数の頂点がなければ,この図にはオーラループも存在することが要求される.オラパスの求め方は簡単で、直接暴力DFSで遡ればいいのですが、この問題で辞書順の最小の頂点を先に行けばOKなのですが、驚くべきことにこのような効率が本当にいいのです.
ps:c++持参のスタックが爆発します.
code

#include
#include
#include
#include
#include
#include
#include

using namespace std;

int edge[3002][3002];
int s[3002];
int n,m;

int gg[30000];

int work(int k)
{
    if ((k>='A')&&(k<='Z'))
        return k-'A'+1;
    else 
        return k-'a'+27;
}  


void prints(int k)
{
     if (k<=26) 
        printf("%c",k+'A'-1);
     else 
         printf("%c",k+'a'-27);
}

int flag=0;

bool dfs(int x,int num)
{
    gg[num+1]=x;
    if (num==m)
    {
        for (int i=1;i<=n+1;i++)
            prints(gg[i]);
        flag=1;
        return true;
    }
    for (int i=1;i<=52;i++)
    {
        if (edge[x][i])
        {
            edge[x][i]=0;
            edge[i][x]=0;
            dfs(i,num+1);
            edge[x][i]=1;
            edge[i][x]=1;
            if (flag)  return true;
        }
    }
    gg[num+1]=0;
    return false;
}

int main()
{
    scanf("%d",&n);
    getchar();
    char x,y;
    m=n;
    for(int i=1;i<=n;i++)
    {
        char ss[3];
        scanf("%s",ss);
        int a=work(ss[0]),b=work(ss[1]);
        edge[a][b]=edge[b][a]=1;
        s[b]++,s[a]++;
    }
    int num=0;
    int small1=1000;
    int small2=1000;

    for (int i=1;i<=52;i++)
        if (s[i]&1) 
            num++,small1=min(small1,i);
        else
            if (s[i]) small2=min(small2,i);
    if ((num!=0)&&(num!=2))
        printf("No Solution");
    int small;
    if (num==0) 
        small=small2;
     else 
        small=small1;
    dfs(small,0);
 }