洛谷1341 无序字母对(欧拉路)
【问题描述】
给定n个各不相同的无序字母对（区分大小写，无序即字母对中的两个字母可以位置颠倒）。请构造一个有n+1个字母的字符串使得每个字母对都在这个字符串中出现。
【输入格式】
第一行输入一个正整数n。
以下n行每行两个字母，表示这两个字母需要相邻。
【输出格式】
输出满足要求的字符串。
如果没有满足要求的字符串，请输出“No Solution”。
如果有多种方案，请输出前面的字母的ASCII编码尽可能小的（字典序最小）的方案
【输入样例】
4
aZ
tZ
Xt
aX
【输出样例】
XaZtX
【数据范围】
【洛谷1341 无序字母对(欧拉路)】不同的无序字母对个数有限，n的规模可以通过计算得到
这道题实质上是无向欧拉路径问题，需判断连个条件，一个是图要基连通，一个是除两个点以外其余点的度要为偶数。这道题我用的是邻接表，不如用邻接矩阵写起来方便。所以在欧拉路问题时可以优先考虑邻接矩阵。
#include
#include
#include
#include
using namespace std;
const int maxn=1000;
vectore;
int n,d[150],s=maxn,vis[maxn];
char ch[maxn][5];
struct data
{
int v,id;
};
vectorg[150];
bool cmp(data a,data b)
{
return a.v=0;
i--)
printf("%c",e[i]);
}
else printf("No Solution\n");
return 0;
}
推荐阅读
- 凛冬将至，保健品行业无序发展的时代结束，重新找回失去的亲情
- C++11中的新容器(array，无序容器，tuple元组)
- 洛谷 P5056 【模板】插头dp
- C++|【暖*墟】 #洛谷省选网课# 8.1数论进阶
- 洛谷|洛谷 P1481 魔族密码
- SP694 DISUBSTR - Distinct Substrings(洛谷 字典树)
- KD-Tree|【NOI2019】【LOJ3259】【洛谷P5471】弹跳（K-D Tree）（最短路）
- JSOI2018冬令营游记&总结（迁移自洛谷博客）
- 洛谷P5471 NOI2019弹跳
- OSG|OSG （三维无序离散点构建Delaunay三角网）