Untitled
By: a guest | Mar 19th, 2010 | Syntax:
None | Size: 1.72 KB | Hits: 70 | Expires: Never
include <cstdio>
include <string>
include <cstring>
include <algorithm>
include <vector>
using namespace std;
define EXT 5
int N;
int V1, V2;
int lastv;
int countv;
int indeg[26];
int outdeg[26];
bool used[26];
bool mat[26][26];
inline int get_number(){
register char c;
register int n = 0;
while((c = getc_unlocked(stdin) ) != '\n'){
n *= 10;
n += ( c - '0' );
}
return n;
}
inline void get_vertexes(){
register char c;
register char t;
V1 = getc_unlocked(stdin)-'a';
while((c = getc_unlocked(stdin)) != '\n'){
t = c;
}
V2 = t-'a';
}
inline void go(int &v){
countv--;
used[v] = false;
for(int i = 0; i < 26; i++){
if(used[i] && mat[v][i]){
go(i);
}
}
}
inline bool solve(){
N = get_number();
memset(mat,false,sizeof(mat));
memset(indeg,0,sizeof(indeg));
memset(outdeg,0,sizeof(outdeg));
memset(used,false,sizeof(used));
while(N--){
get_vertexes();
outdeg[V1]++;
indeg[V2]++;
used[V1] = true;
used[V2] = true;
lastv = V1;
mat[V1][V2] = true;
}
int count = 0;
int p[2];
countv = 0;
for(int i = 0; i < 26; i++){
if(used[i]){
countv++;
if(indeg[i]!=outdeg[i]){
if(count>=2) return false;
p[count] = i;
count++;
}
}
}
if(count==1) return false;
if(count==2){
int v1 = p[0];
int v2 = p[1];
if(indeg[v1]>outdeg[v1]){
if(indeg[v1]-outdeg[v1]!=1) return false;
if(outdeg[v2]-indeg[v2]!=1) return false;
mat[v1][v2] = true;
}else{
if(indeg[v2]-outdeg[v2]!=1) return false;
if(outdeg[v1]-indeg[v1]!=1) return false;
mat[v2][v1] = true;
}
}
go(lastv);
return countv == 0;
}
int main(){
int T = get_number();
while(T--){
if(solve()){
fputs_unlocked("Ordering is possible.\n", stdout);
}else{
fputs_unlocked("The door cannot be opened.\n", stdout);
}
}
}