UVAOJ10129 | 哈喽哈咯

Written by razrlele 21:39 February 19, 2015

欧拉回路，当然准确来说应该归到Eulerlan Path而不是 Eulerlan Cycle，两者的区别就是前者除了两个点之外所有点出度和入度都相等，而剩下的两个点一个点的入度比出度大一，另外一个出度比入度大一，后者则是所有的点的出度入度都相等。

不过这个题目里面也考虑到了Eulerlan Cycle的情况，但是是以Eulerlan Path为主。

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

/********************************************************

* File Name: uvaoj10129.cpp

* Author: razrLeLe

* Mail: razrlele@gmail.com

* Homepage: https://yueyu.io

* Created Time: Mon 16 Feb 2015 12:28:06 PM CST

******************************************************/

#include "vector"

#include "set"

#include "deque"

#include "queue"

#include "algorithm"

#include "functional"

#include "iostream"

#include "cstdio"

#include "cmath"

#include "cstdlib"

#include "string"

#include "cstring"

#include "string.h"

#include "map"

#include "cctype"

#include "list"

#include "stack"

using namespace std;

#define INF 0x3f3f3f3f

#define LOCAL

const int maxn = 30;

int grid[maxn][maxn];

bool vis[maxn];

int dif[maxn];

int cnum;

bool orderred, existed[maxn];

int one, subone;

void DFS(int a, int &count)

{

vis[a] = true;

count++;

for(int i = 0; i < 26; i++)

{

if(grid[a][i] && !vis[i])

DFS(i, count);

}

return ;

}

int main()

{

#ifdef LOCAL

freopen("/home/razrlele/build/data.txt", "r", stdin);

freopen("/home/razrlele/build/out.txt", "w", stdout);

#endif

int T, N;

scanf("%d", &T);

while(T--)

{

orderred = true;

memset(grid, 0, sizeof(grid));

memset(vis, false, sizeof(vis));

memset(dif, 0, sizeof(dif));

memset(existed, false, sizeof(existed));

cnum = 0;

string tmp;

scanf("%d", &N);

for(int i = 0; i < N; i++)

{

cin >> tmp;

int a = tmp[0] - 'a';

int b = tmp[tmp.length()-1]-'a';

grid[a][b] = 1;

grid[b][a] = 1;

dif[a]++;

dif[b]--;

existed[a] = true;

existed[b] = true;

}

for(int i = 0; i < 26; i++)

{

if(existed[i])

cnum++;

}

one = subone = 0;

for(int i = 0; i < 26; i++)

{

if(dif[i] == -1)

subone++;

else if(dif[i] == 1)

one++;

else if(dif[i] != 0)

{

orderred = false;

break;

}

if(!(subone==one && (one==1 || one ==0)))

orderred = false;

if(orderred)

{

for(int i = 0; i < 26; i++)

{

if(existed[i])

{

int count = 0;

DFS(i, count);

if(count != cnum)

{

orderred = false;

}

break ;

}

if(orderred)

printf("Ordering is possible.\n");

else

printf("The door cannot be opened.\n");

}

return 0;

}