【紫书】Play on Words UVA - 10129 欧拉回路

时间:2022-12-07 14:41:59

题意:给你1e5个字符串,若前一个的末尾字母等于当前的首字母,则可以连在一起(成语接龙一个意思)判断是否可以将他们连在一起

题解:将首位看作点,单词看作边。变成欧拉回路问题。

    判断出入度是否相等,再用并查集判一下连通性

    (dfs/bfs也行:随便取一个点,搜索一遍。如果每个点都被标记,则是连通的。)

ac代码:

#define _CRT_SECURE_NO_WARNINGS
#include "stdio.h"
#include<stdio.h>
#include<algorithm>
#include<string>
#include<vector>
#include<list>
#include<set>
#include<iostream>
#include<string.h>
#include<queue>
#include<string>
#include<sstream>
#include<stack>
#include<cmath>
using namespace std;
const int maxn = 1e5 + ;
char s[maxn][];
char ss[];
int in[], out[];
//两个点入度不等于出度且一个差+1,一个-1
int f[];
int find(int x) {
return f[x] == x ? x : f[x] = find(f[x]);
}
void un(int x, int y) {
int u = find(x);
int v = find(y);
f[u] = v;
}
bool same(int x,int y) {
return find(x) == find(y);
}
int main() {
int t; cin >> t; while (t--) {
int n; cin >> n;
for (int i = ; i < ; i++) f[i] = i;
memset(in, , sizeof(in)); memset(out, , sizeof(out));
for (int i = ; i < n; i++) {
scanf("%s", ss);
int len = strlen(ss);
out[ss[]]++; in[ss[len - ]]++;
un(ss[], ss[len - ]); }
int ok = ; //连通
int yes = ;//出入度
vector<int> temp;
for (int i = 'a'; i <= 'z'; i++)if(out[i]+in[i]) {//出现过的字母
if (!same('a', i)) { ok = ; break; }
if (out[i] != in[i]) {
temp.push_back(i);
}
} if (temp.size() == ) {
int f = temp.front(), b = temp.back();
if ((abs(in[f] - out[f]) == ) && (abs(in[b] - out[b]) == ) && (in[f] + in[b] == out[f] + out[b]))yes=;
}
else if (temp.size() == )yes = ; if (ok&&yes)cout << "Ordering is possible.\n";
else cout << "The door cannot be opened.\n"; } system("pause");
return ;
}