关键字：欧拉路。
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；如果有两个度数为奇数的点，那么选择两个点中字典序小的点开始走；如果都是度数为偶数的点，那么选择所有点中字典序最小的点开始。
#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)
