关键字：欧拉路。
Link&Limit
时间限制：1000ms 空间限制：131072kb
Description
给定n个各不相同的无序字母对（区分大小写，无序即字母对中的两个字母可以位置颠倒）。请构造一个有n+1个字母的字符串使得每个字母对都在这个字符串中出现。
Input Format
第一行输入一个正整数n。
以下n行每行两个字母，表示这两个字母需要相邻。
Output Format
输出满足要求的字符串。
如果没有满足要求的字符串，请输出“No Solution”。
如果有多种方案，请输出前面的字母的ASCII编码尽可能小的（字典序最小）的方案。
Sample Input #1
4
aZ
tZ
Xt
aX
Sample Output #1
XaZtX
Hint
不同的无序字母对个数有限，n的规模可以通过计算得到。
哥尼斯堡七桥边我们的连线~本题就是一个欧拉路问题。“两个字母需要相邻”，这样的条件就相当于在两个字母之间连一条无向边。把n条无向边都走一遍，正好 走过n+1个节点，符合题目要求。所以，我们只要判断构造出的图是否符合欧拉路的条件。如果不符合，或者图不连通，就是No Solution；如果有两个度数为奇数的点，那么选择两个点中字典序小的点开始走；如果都是度数为偶数的点，那么选择所有点中字典序最小的点开始。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 | #include <stdio.h>int n,deg[210],ansCnt = 0;int g[210][210],p[210];short vis[210][210],ok = 0;char ans[1010];int min(int a,int b){ return a<b?a:b;}void dfs(int sn){ int fn; ans[++ansCnt] = (char)sn; if(ansCnt>=n+1) { ok = 1; return;} for(fn='A';fn<='z';fn++) { if(!g[sn][fn] || vis[sn][fn]) continue; vis[sn][fn] = vis[fn][sn] = 1; dfs(fn); if(ok) return; vis[sn][fn] = vis[fn][sn] = 0; } ansCnt--;}int main(){ int i; char sn,fn; scanf("%d\n",&n); for(i=1;i<=n;i++) { scanf("%c%c\n",&sn,&fn); g[(int)sn][(int)fn] = g[(int)fn][(int)sn] = 1; deg[(int)sn]++; deg[(int)fn]++; } sn = fn = 0; for(i='A';i<='z';i++) { if(deg[i]&1) { if(!sn) sn = i; else if(!fn) fn = i; else break; } } if(i<='z') { printf("No Solution"); return 0;} if(!sn) for(i='A';i<='z';i++) { if(deg[i]) { dfs(i); break;} } else dfs(min((int)sn,(int)fn)); if(ok) printf("%s",ans+1); else printf("No Solution"); return 0;} |
评论 (0)
