这是一道欧拉路径的问题
欧拉路径：对于无向图，当且仅当奇数度为0或2时，存在欧拉路径，即可以不重复的经过每一条边。
（1）当奇数度为0时，即所有节点的边数都是偶数时，肯定能回来（n条边，n/2条出来，n/2条回来），故叫做欧拉回路
（2）当奇数度为2时，这两个相应的奇数度节点一定一个是起点，一个是终点，否则做不到不重复的经过每一条边。
*************************************
对于这题，可以把字母对拆开，
对于样例：
4 aZ tZ Xt aX 可拆成：a Z t X然后连无向边，比如aZ就把a和Z连起来
计算节点的度数，相应的按照欧拉路径来处理，
对于（1），可按照优先级搜索，保存边的vector可以排序，很方便
对于（2），设两点为v u，如果v<u直接以v为起点搜下，否则以u为起点搜下
注意：记录使用的b数组（或者说“used”数组），是记录边的使用，不是节点的使用情况
如果记录节点，那么可能是aZ Zt ta，这样会炸的。
***************************************
#include<cstdio> #include<cstdlib> #include<iostream> #include<algorithm> #include<vector> #define MAXN 3005 #define MAXM 65 using namespace std; int n; vector<int> G[MAXM]; int b[MAXM][MAXM]; int ans[MAXN]; int temp[MAXM]; int cnt; int dfs(int x,int k){ if(k>n-cnt){ return 1; } for(int i=0;i<G[x].size();i++){ int y=G[x][i]; if(!b[x][y]){ b[x][y]=b[y][x]=1; if(dfs(y,k+1)){ ans[k]=y; return 1; } b[x][y]=b[y][x]=0; } } } int read(){ scanf("%d",&n); for(int i=1;i<=n;i++){ char x,y; cin>>x>>y; x-='A'; y-='A'; if(x==y){ G[x].push_back(y); } else{ G[x].push_back(y); G[y].push_back(x); temp[x]++; temp[y]++; } } for(int i=0;i<MAXM;i++){ sort(G[i].begin(),G[i].end()); } int cnt=0; for(int i=0;i<MAXM;i++){ if((temp[i]&1)){ cnt++; } } // for(int i=0;i<MAXM;i++){ // if(G[i].size()){ // for(int j=0;j<G[i].size();j++) // printf("(%c,%c)\n",i+'A',G[i][j]+'A'); // } // } if(cnt&&cnt!=2){ printf("No Solution\n"); return 1; } if(cnt){ int u=0,v=0; for(int i=0;i<MAXM;i++){ if((temp[i]&1)){ if(u){ v=i; break; } else{ u=i; } } } if(u<v){ ans[0]=u; dfs(u,1); } else{ ans[0]=v; dfs(v,1); } for(int i=0;i<=n;i++){ printf("%c",ans[i]+'A'); } return 1; } return 0; } int main() { // freopen("data.in","r",stdin); // freopen("my.out","w",stdout); if(read()) return 0; cnt=1; for(int i=0;i<MAXM;i++){ if(temp[i]){ ans[0]=i; ans[n]=i; if(dfs(i,1)){ for(int i=0;i<=n;i++){ printf("%c",ans[i]+'A'); } return 0; } } } return 0; }
