CF 508D Tanya and Password（无向图+输出欧拉路）

(￣▽￣)"

//不知道为什么，用scanf输入char数组的话，字符获取失效
//于是改用cin>>string，就可以了
//这题字符的处理比较麻烦，输入之后转成数字，用到函数get(char),get_num(string,int)
//最后字符的输出是反向输出的，用到函数get_char(int)
//这道题也算是到无向图输出欧拉路的模板题，判有无欧拉路用到函数ok()
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<string>
#include<cstdlib>
#include<vector>
#include<stack>
using namespace std;
typedef long long ll;
const int MAXN=200010;

struct node
{
    int next;  //E[i].next指向图中与i同父的下一个结点
    int to;  //E[i].to指向图中i的子结点
}E[MAXN];

int vis[MAXN],fa[MAXN]; //vis:两字符构成串映射的点
int in[MAXN/2],ans[MAXN];
int cnt,pcnt,n,st,flag1,flag2; //cnt:边下标 pcnt:点下标 n:串数 st:图遍历的起点

void add(int u,int v)
{
    E[cnt].to=v;
    E[cnt].next=fa[u];
    fa[u]=cnt++;
    return ;
}

int get(char s)
{
    if(s>='0'&&s<='9') return s-'0';
    else if(s>='a'&&s<='z') return s-'a'+10;
    else return s-'A'+36;
}

int get_num(string s,int index)
{
    if(index==0)
        return get(s[0])*100+get(s[1]);
    else
        return get(s[1])*100+get(s[2]);
}

char get_char(int x)
{
    if(x<10) return x+'0';
    if(x<36) return x-10+'a';
    return x-36+'A';
}

void init()
{
    scanf("%d",&n);
    cnt=0;pcnt=0;
    memset(fa,-1,sizeof(fa));
    memset(vis,-1,sizeof(vis));
    memset(in,0,sizeof(in));
    string str;

    for(int i=0;i<n;i++)
    {
        cin>>str;
        int u=get_num(str,0);
        int v=get_num(str,1);
        add(u,v);

        if(vis[u]==-1)  //vis[u]记录边权为u的点是第几个被访问的
        {
            vis[u]=pcnt;
            ans[pcnt++]=u;  //点下标++
        }
        if(vis[v]==-1)
        {
            vis[v]=pcnt;
            ans[pcnt++]=v;
        }
        //边1从vis[u]点连出，边2从vis[v]点连入
        in[vis[u]]++;  //第vis[u]个点的度++
        in[vis[v]]--;
    }
}

void DFS(int x)
{
    for(int i=fa[x];i!=-1;i=fa[x])
    {
        if(vis[i]==0)
        {
            vis[i]=1;
            fa[x]=E[i].next;
            DFS(E[i].to);
        }
    }
    ans[pcnt++]=x;
}

bool ok()
{
    int i;
    flag1=0,flag2=0;
    for(i=0;i<pcnt;i++)
    {
        if(in[i]<-1||in[i]>1) //<-1表示入度大于1,>1表示出度大于1
            break;  //此时此图一定无法形成欧拉路
        if(in[i]==1)
            flag1++;
        if(in[i]==-1)
            flag2++;
    }
    if(i<pcnt || !(flag1==flag2 && flag1<=1))
        return false;
    else
        return true;
}

int main()
{
    init();

    if(ok())
    {
        st=ans[0];
        for(int i=0;i<pcnt;i++)
            if(in[i]==1)
                st=ans[i];  //st记录图起点
        pcnt=0;
        memset(vis,0,sizeof(vis));

        //以上找起点、清零是为DFS做准备
        DFS(st);
        if(pcnt<n+1)
            printf("NO
");
        else
        {
            printf("YES
");
            printf("%c%c",get_char(ans[pcnt-1]/100),get_char(ans[pcnt-1]%100));
            for(int i=pcnt-2;i>=0;i--)
                printf("%c",get_char(ans[i]%100));
            printf("
");
        }
    }
    else
        printf("NO
");
    return 0;
}