洛谷 P1341 无序字母对(欧拉路)

/*

欧拉路.

n的规模应该是A(26,2)=26*25=650.

这题主要是要建模能想到欧拉路.

因为要求字典序最小.

so 找奇点的时候找字典序最小的.

(因为保证第一个最小就保证了字典序最小)

然后[1,52] 有52个字母循环.

天然的循环顺序保证了字典序最小hhh.

一开始还是用性质判有没有解.

然后dfs跑欧拉路记录路径就ok了.

*/

#include<iostream>

#include<cstdio>

#include<cstring>

#define MAXN 1001

#define MAXM 61

using namespace std;

int in[MAXM],out[MAXM],tot,n,g[MAXM][MAXM],d[MAXN],s1=1e4,s2=1e4,ans[MAXN];

char s[3];

bool b[MAXM],flag;

int read()

{

    int x=0,f=1;char ch=getchar();

    while(ch<'0'||ch>'9') {if(ch=='-')f=1;ch=getchar();}

    while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();

    return x*f;

}

void dfs(int u,int t)

{

    ans[t]=u;

    if(t==n+1)

    {

        flag=true;return ;

    }

    b[u]=true;

    for(int i=1;i<=52;i++)

    {

        if(g[u][i])

        {

            g[u][i]=g[i][u]=false;

            dfs(i,t+1);

            if(flag) return ;

            g[u][i]=g[i][u]=true;

        }

    }

     return ;

}

int Get(char ch)

{

    return ch>='a'&&ch<='z'?ch-70:ch-64;

}

char Go(int ch)

{

    return ch>=1&&ch<=26?ch+64:ch+70;

}

int main()

{

    int l,x,y;

    n=read();

    for(int i=1;i<=n;i++)

    {

        cin>>s;l=strlen(s);x=Get(s[0]),y=Get(s[1]);

        out[x]++,in[y]++;;

        g[x][y]=true;g[y][x]=true,d[x]++,d[y]++;

    }

    for(int i=1;i<=52;i++)

      if(d[i]&1) tot++;

    if(tot>2)

    {

        printf("No Solution");

        return 0;

    }

    for(int i=1;i<=52;i++)

      if(d[i]&1) {s1=i;break;}

    if(s1!=1e4) dfs(s1,1);

    else

    {

        for(int i=1;i<=52;i++)

          if(d[i]) {s1=i;break;}

        dfs(s1,1);

    }

    for(int i=1;i<=n+1;i++) printf("%c",Go(ans[i]));

    return 0;

}