无序字母对（luogu 1314）

题目描述

给定n个各不相同的无序字母对（区分大小写，无序即字母对中的两个字母可以位置颠倒）。请构造一个有n+1个字母的字符串使得每个字母对都在这个字符串中出现。

输入输出格式

输入格式：

第一行输入一个正整数n。

以下n行每行两个字母，表示这两个字母需要相邻。

输出格式：

输出满足要求的字符串。

如果没有满足要求的字符串，请输出“No Solution”。

如果有多种方案，请输出前面的字母的ASCII编码尽可能小的（字典序最小）的方案

输入输出样例

4
aZ
tZ
Xt
aX

XaZtX

说明

【数据规模与约定】

不同的无序字母对个数有限，n的规模可以通过计算得到。

code

#include
#include 
#include 
using namespace std;
const int mxn=300;
int n,du[mxn],fa[mxn],v[mxn][mxn];
char ans[mxn];int Find(int x) {return x==fa[x]?x:fa[x]=Find(fa[x]);
}void dfs(int x) {for(int i=1;i<=mxn;++i) if(v[x][i]) {v[x][i]=v[i][x]=0;dfs(i);}ans[n--]=x;
}int main() 
{scanf("%d",&n);for(int i=1;i<=mxn;++i) fa[i]=i;for(int i=1;i<=n;++i) {char ch[5];scanf("%s",ch);int x=ch[0],y=ch[1];v[x][y]=v[y][x]=1;du[x]++,du[y]++;fa[Find(x)]=Find(y);}int st=0,jud=0,cnt=0;for(int i=1;i<=mxn;++i) //判断连通性if(fa[i]==i && du[i]) jud++;if(jud!=1) {printf("No Solution");return 0;}  for(int i=1;i<=mxn;++i) if(du[i]&1) { //盼奇点（链） cnt++;if(!st) st=i;} if(!st) // 判环，找到最小点 for(int i=0;ii) if(du[i]) {st=i;break;}if(cnt && cnt!=2) {printf("No Solution");return 0;} dfs(st);puts(ans);return 0;
}
/*
5
ab
ac
ad
ae
af3
ab
ac
ad
*/

转载于:https://www.cnblogs.com/qseer/p/9822343.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！