传送门: UVA - 10129
题目大意:
给定一些单词(可能会重复出现),判断单词是否能排成一个序列,前提是单词的最后一个字母与下一个单词的第一个字母相同.输出"The door cannot be opened."(不可能)或者"Ordering is possible."(可能).
单词数小于 10,000,且单个测试的有多组数据.
解题思路:
将单词看作链接首尾字母的边,建图,寻找 一条欧拉路径.(E.P.),需要判断底图(即无向图 或 由有向图看作的无向图)是否连通(连接性),其次是端点的度数(除起始点外(度数为奇),其他点入度应总是等于出度).其中判断来连接性的算法有(紫书P169):
算法一:DFS
判断能否用邻接表遍历所有边即可,代码后续补上.
算法二:UFS
用并查集判断连通(最适合不过了),详细代码(改自GitHub)
// 题意：输入n个单词，是否可以排成一个序列，使得每个单词的第一个字母和上一个单词的最后一个字母相同
// 算法：把字母看作结点，单词看成有向边，则有解当且仅当图中有欧拉路径。注意要先判连通
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
+ ;
// 并查集（代码摘自《算法竞赛入门经典——训练指南》第三章）
];
int findset(int x) { return pa[x] != x ? pa[x] = findset(pa[x]) : x; }
], deg[]; // 是否出现过；度数
int main() {
int T;
scanf("%d", &T);
while(T--) {
int n;
char word[maxn];
scanf("%d", &n);
memset(used, , sizeof(used));
memset(deg, , sizeof(deg));
for(int ch = 'a'; ch <= 'z'; ch++) pa[ch] = ch; // 初始化并查集
; // 连通块个数
; i < n; i++) {
scanf("%s", word);
], c2 = word[strlen(word)-];
deg[c1]++;//出度增
deg[c2]--;//入度减 <---这份代码的神奇之处
used[c1] = used[c2] = ;
int s1 = findset(c1), s2 = findset(c2);
if(s1 != s2) { pa[s1] = s2; cc--; }//容易写错
}
vector<int> d;
for(int ch = 'a'; ch <= 'z'; ch++) {
if(!used[ch]) cc--; // 没出现过的字母
) d.push_back(deg[ch]);
}
bool ok = false;//只存在一个连通块为: 欧拉回路|| 欧拉路径
&& (d.empty() || (d.size() == && (d[] == || d[] == -)))) ok = true;
if(ok) printf("Ordering is possible.\n");
else printf("The door cannot be opened.\n");
}
;
}