主要是求能否形成联通的欧拉回路
并查集+ 欧拉回路判断
一开始用dfs判断联通,死活A不出来,Wa了好多次………哭……
并查集一次就AC了
感觉还是并查集代码好写一点,
因为dfs还要判断入口在哪里……2333333
判断欧拉回路:
1.判断联通(dfs|并查集)
2.判断欧拉回路的条件(1.要么所有的点出度等于入度,2.要么只能有一个出度比入度大于1(入口),一个入度比出度小于1(出口)其他的点必须出度等于入度)
代码:
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <stack>
#include <cctype>
#include <string>
#include <malloc.h>
#include <queue>
#include <map> using namespace std;
const int INF = 0xffffff;
const double Pi = * atan();
const int Maxn = + ;
//int dir2[8][2] = {{-1,0},{0,-1},{-1,1},{1,-1},{-1,-1},{1,0},{0,1},{1,1}}; int in[];
int out[];
int f[]; int _f(int i){
if(f[i] == i)
return i;
return _f(f[i]);
} int main()
{
#ifndef ONLINE_JUDGE
freopen("inpt.txt","r",stdin);
#endif
int t;
cin >> t;
int n;
while(t--){
cin >> n;
memset(in,,sizeof(in));
memset(out,,sizeof(out));
for(int i = ;i < ;i++)
f[i] = i;
while(n--){
char str[];
cin >> str;
int len = strlen(str);
in[ str[] - 'a' ]++;
out[ str[len-] - 'a' ]++;
int x = _f( str[] - 'a' );
int y = _f( str[len-] - 'a');
if(x != y)
f[x] = y;
}
int cnt = ;
int start = ;
int enn = ;
for(int i = ;i < ;i++){
if(in[i] != out[i]){
cnt++;
if(in[i] - out[i] == )
start++;
else if(out[i] - in[i] == )
enn++;
else
cnt = ;
if(cnt > )
break;
}
}
bool flag = ;
if(start == && enn == && cnt == ){
flag = ;
}
else if(cnt == ){
flag = ;
}
if(!flag){
for(int i = ;i < ;i++){
if(in[i] || out[i]){
for(int j = ;j < ;j++){
if( (in[j] || out[j] ) && _f(i) != _f(j)){
flag = ;
break;
}
}
break;
}
}
}
if(flag)
cout << "The door cannot be opened." << endl;
else
cout << "Ordering is possible." << endl;
}
return ;
}