?
第一次做输出欧拉路径的题。用dfs搜。
先对每个单词拆成前两个一组，后两个一组，然后对这两组加边并标号。比如“abc”，拆成“ab”和“bc”，然后对ab和bc所属的编号加边。然后深搜，并记录路径。需要注意的是，用前向星的话，需要再深搜的时候让前面走过的边后边不用再走，而且也要回溯的时候后边走过的前面的也不再走。简单处理下就行了。
代码如下：
#include #include #include #include #include #include #include #include #include using namespace std; #define LL __int64 #define pi acos(-1.0) const int mod=1e9+7; const int INF=0x3f3f3f3f; const double eqs=1e-9; int in[4000], out[4000], cnt, head[4000], tot, vis[210000], path[210000], top; char st[210000][4]; int id[4000]; struct node { int u, v, next; } edge[410000]; void add(int u, int v) { edge[cnt].v=v; edge[cnt].next=head[u]; head[u]=cnt++; } void dfs(int u, int id) { for(int i=head[u]; i!=-1; i=edge[i].next) { if(!vis[i]) { vis[i]=1; head[u]=i; dfs(edge[i].v,i); } i=head[u]; } path[top++]=id; } int getid(char *s) { int ans=0,tmp; for(int i=0;i<2;i++){ if(s[i]>='a'&&s[i]<='z') tmp=s[i]-'a'; else if(s[i]>='A'&&s[i]<='Z') tmp=s[i]-'A'+26; else tmp=s[i]-'0'+52; ans=ans*62+tmp; } return ans; } void init() { memset(in,0,sizeof(in)); memset(out,0,sizeof(out)); memset(head,-1,sizeof(head)); memset(vis,0,sizeof(vis)); memset(id,0,sizeof(id)); cnt=tot=0; } int main() { int n, i, flag, sum=0, pos, num1, num2; char s1[3], s2[3]; scanf(%d,&n); init(); getchar(); for(i=0; i 1) { flag=1; break; } } if(flag||sum>2) { printf(NO ); } else { top=0; dfs(pos,-1); //printf(%d ,top); if(top!=n+1) { printf(NO); } else { printf(YES ); //printf(---%d ,path[top-2]); printf(%s,st[path[top-2]]); for(i=top-3; i>=0; i--) { printf(%c,st[path[i]][2]); } } } return 0; }