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\n");
else
{
printf("YES\n");
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("\n");
}
}
else
printf("NO\n");
return 0;
}