//有向图欧拉回路 + 并查集判连通性
#include<iostream>
#include<fstream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<ctype.h>
#include<algorithm>
#include<string>
#define PI acos(-1.0)
#define maxn 1000
#define INF 1<<25
#define mem(a, b) memset(a, b, sizeof(a))
typedef long long ll;
using namespace std;
int f[30];
int find(int x)
{
if (f[x] != x) f[x] = find(f[x]);
return f[x];
}
int main ()
{
int i, j, t, n;
cin>>t;
while(t--)
{
bool has[30] = {false};
int sum = 0, a[30] = {0};
char str[1010];
for (i = 0; i < 26; i++) f[i] = i;
cin>>n;
getchar();
while(n--)
{
gets(str);
int u = str[0] - ‘a‘, v = str[strlen(str) - 1] - ‘a‘;
a[u]--;
if (!has[u])
has[u] = true;
a[v]++;
if (!has[v])
has[v] = true;
f[find(u)] = find(v);
}
int no = 0, out = 0, in = 0;
for (i = 0; i < 26; i++) if (a[i])
{
no++;
if (a[i] == 1) in++;
if (a[i] == -1) out++;
}
for (i = 0; i < 26; i++) if (has[i] && f[i] == i) sum++;
if (sum == 1 && (no == 0 || (no == 2 && out == 1 && in == 1))) puts("Ordering is possible.");
else puts("The door cannot be opened.");
}
return 0;
}//有向图欧拉回路 + bfs判连通性
#include<iostream>
#include<fstream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<ctype.h>
#include<algorithm>
#include<string>
#define PI acos(-1.0)
#define maxn 1000
#define INF 1<<25
#define mem(a, b) memset(a, b, sizeof(a))
typedef long long ll;
using namespace std;
int mp[30][30];
int bfs(int x) // 必须是对有出度的字母进行bfs!
{
int vis[30] = {0}, font = 0, rear = 1, sum = 1;
int que[1000] = {0};
que[font] = x;
vis[x] = 1;
int u, next;
while(font < rear)
{
u = que[font++];
for (int v = 0; v < 26; v++) if (mp[u][v] && !vis[v])
{
vis[v] = 1;
sum++;
que[rear++] = v;
}
}
return sum;
}
int main ()
{
int i, j, t, n;
cin>>t;
while(t--)
{
bool has[30] = {false};
int sum = 0, a[30] = {0}, k;
char str[1010];
mem(mp, 0);
cin>>n;
getchar();
while(n--)
{
gets(str);
int u = str[0] - ‘a‘, v = str[strlen(str) - 1] - ‘a‘;
a[u]--;
if (!has[u])
has[u] = true, sum++;
a[v]++;
if (!has[v])
has[v] = true, sum++;
mp[u][v] = mp[v][u] = 1;
k = u;
}
int no = 0, out = 0, in = 0;
for (i = 0; i < 26; i++) if (a[i])
{
no++;
if (a[i] == 1) in++;
if (a[i] == -1) out++;
}
if (sum == bfs(k) && (no == 0 || (no == 2 && out == 1 && in == 1))) puts("Ordering is possible.");
else puts("The door cannot be opened.");
}
return 0;
}原文:http://blog.csdn.net/sio__five/article/details/18660555