uva 10129 - Play on Words

点击打开链接

题目意思：给定n个单词，要求单词的第一个字母和前一个单词的最后字母相同（除了第一个），判断所有单词是否可以连成一条链。

解题思路：题目很明显是一个有关欧拉路的问题，我们先了解一下有关欧拉道路和欧拉回路的区别。欧拉道路是分为有向和无向两种，对于欧拉道路上的节点有两种度，入度和出度，入度表示进入该节点次数，出度表示出去该节点的次数，对于一条普通的有向欧拉道路来说存在一个起点和终点，并且起点的入度比出度小1，终点的入度比出度大1，下面介绍特殊的欧拉道路-----欧拉回路，欧拉回路是起点和终点重合，并且所有的节点的度都相同都为偶数。

有了这些知识，介绍解题方法，首先我们用两个数组in out来存储每个单词的首字母和末尾字母的入度和出度，还用一个map二维数组作为点的邻阶矩阵。

第一步 读完字符串后判断是否可以构成欧拉道路，利用性质判断，即每一个节点的入度和出度差的范围是-1～1，超过这个范围即可判断不满足。

第二步 如果是欧拉道路的话，我们可以用dfs来搜索第一个有出度的单词，这时候的搜索是不用考虑方向的，即用到我们刚才建的map二维数组，用一个同一大小的 二 维数组记录走过的单词，如果刚好把map对应的单词全部标记，说明已经可以链接成一条链。（这里可以用并查集）

注意事项：对于欧拉道路来说，是否是连通的就是判断从某个点能否遍历所有的点，这时候要建立一个无向图的邻阶矩阵（判断连通都是当成无向图判断）

代码：

//对于欧拉道路来说，是否是连通的就是判断从某个点能否遍历所有的点，这时候要建立一个无向图的邻阶矩阵（判断连通都是当成无向图判断）
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <queue>
using namespace std;
const int MAXN = 30;

int t, n, flag;
int out[MAXN], in[MAXN];
int vis[MAXN][MAXN] , map[MAXN][MAXN];
//深搜
void dfs(int pos) {
 for(int i = 0 ; i < 26 ; i++){
 if(map[pos][i] && vis[pos][i] == 0){
 vis[pos][i] = 1;//标记为1
 dfs(i);//继续搜索
 }
 }
}

void solve() {
 int i , j , cnt;
 flag = 1;//初始化为1
 for (i = 0; i < 26; i++) {//判断是否满足欧拉道路的性质
 if (out[i] - in[i] < -1 || out[i] - in[i] > 1){
 flag = 0;
 return;
 }
 }
 for(i = 0 ; i < 26 ; i++){
 if(out[i]){//找到一个有出度的直接搜索
 dfs(i);
 break;//这里要跳出循环
 }
 }
 for(i = 0 ; i < 26 ; i++){
 for(j = 0 ; j < 26 ; j++){
 if(map[i][j] && vis[i][j] == 0){//判断是否可以连成链
 flag = 0;
 return;
 }
 }
 }
}

int main() {
 int i;
 scanf("%d", &t);
 while (t--) {
 scanf("%d", &n);
 string str;
 memset(out, 0, sizeof (out));
 memset(in, 0, sizeof (in));
 memset(map , 0 , sizeof(map));
 memset(vis , 0 , sizeof(vis));
 for (i = 0; i < n; i++) {
 cin>>str;
 int len = str.size();
 int x = str[0] - 97;
 int y = str[len-1] - 97;
 out[x]++;
 in[y]++;
 //无向图的邻阶矩阵
 map[x][y]++;
 map[y][x]++;
 }
 if (n == 1)//对于1的特判
 flag = 1;
 if (n > 1)
 solve();
 if (flag)
 printf("Ordering is possible.\n");
 if (flag == 0)
 printf("The door cannot be opened.\n");
 }
}