UVa 10129单词(欧拉回路)

时间:2021-09-28 07:03:58

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1070

题意是输入n个单词,是否可以把所有这些单词排成一个序列,使得每个单词的第一个字母和上一个单词的最后一个字母相同。输入中可以有重复单词。

由于最后只需要判断是否能排成这样的一个序列,所以没有输入单词后,只需要把首尾字母保存下来,然后可以dfs深度递归。由于可能会有重复单词,在这里可以设一个times数组来记录单词所用的次数。

 #include<iostream>
#include<cstring>
using namespace std; int map[][];
int times[][];
int number; void dfs(int u,int v)
{
number++;
for (int i = ; i < ; i++)
{
if (map[v][i]> && times[v][i] < map[v][i])
{
times[v][i]++;
dfs(v, i);
}
}
} int main()
{
char s[];
int t;
cin >> t;
while (t--)
{
int n,p;
cin >> n;
p = n;
memset(s, , sizeof(s));
memset(map, , sizeof(map));
int k = ,u,v,l;
while (n--)
{
cin >> s;
u = s[] - 'a';
l = strlen(s);
v = s[l - ] - 'a';
map[u][v]++;
}
int flag;
for (int i = ; i < ; i++)
{
flag = ;
for (int j = ; j < ; j++)
{
if (map[i][j]>)
{
number = ;
times[i][j]++;
dfs(i,j);
memset(times, , sizeof(times));
if (number == p) { flag = ; break; }
}
}
if (flag == ) break;
}
if (flag == ) cout << "The door cannot be opened." << endl;
else cout << "Ordering is possible." << endl;
}
return ;
}