UVa 10129单词（Play on Words）
发布时间
阅读量：
阅读量
给定n个单词，能否将它们排列成一个序列，使得每个单词的首字母与前一个单词的末字母相匹配？每个单词最多由1000个英文小写字母组成，输入中可能存在重复的单词。
这一问题实际上等价于判断是否存在有向图中的欧拉路径。具体条件如下：
- 图中所有节点必须处于同一连通分量（可通过并查集实现判断）
- 存在一个节点的入度比出度少1，作为终点；同时存在另一个节点的出度比入度少1，作为起点；其余所有节点的入度与出度之差必须为偶数，并且仅有两个节点具有奇数的入度或出度差异
关于欧拉回路的相关知识，可参考
至于并查集的相关内容，建议自行查阅相关资料
#include<bits/stdc++.h>
using namespace std;
int in[26];
int out[26];
int p[26];
bool vis[26];
//并查集
void init() {
for(int i = 0;i < 26; i++) {
p[i] = i;
}
}
int find(int a) {
while(a != p[a]) {
a = p[a];
}
return a;全部评论 (0)
还没有任何评论哟~