| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 11838 | Accepted: 4048 |
Description
Input
Output
Sample Input
3 2 acm ibm 3 acm malform mouse 2 ok ok
Sample Output
The door cannot be opened. Ordering is possible. The door cannot be opened.
题目链接：POJ 1386
对于是否是欧拉图的判断：首先基图要连通，然后再看入度和出度不相等的点的个数，若为0，则为欧拉图且有欧拉回路；如果为1，即只有一个点入度不等于其他点均相等，则出度不会等于入度，显然这在图里是不可能的，图的入度和一定会等于出度和；然后是两个点，看是否一个是入度比出度少1，一个是入度比出度多1……，忘记判断vector为空RE几次…………
代码：
#include <stdio.h>
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define CLR(x,y) memset(x,y,sizeof(x))
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
typedef pair<int,int> pii;
typedef long long LL;
const double PI=acos(-1.0);
const int N=100010;
const int L=1005;
char s[L];
struct edge
{
int to;
int pre;
};
edge E[N<<1];
int head[N],tot;
int cur[30],vis[30];
int ru[30],chu[30];
void init()
{
CLR(head,-1);
tot=0;
CLR(vis,0);
CLR(cur,0);
CLR(ru,0);
CLR(chu,0);
}
void add(int s,int t)
{
E[tot].to=t;
E[tot].pre=head[s];
head[s]=tot++;
}
bool bfs(int s,int all)
{
queue<int>Q;
vis[s]=1;
--all;
Q.push(s);
while (!Q.empty())
{
int now=Q.front();
Q.pop();
for (int i=head[now]; ~i; i=E[i].pre)
{
int v=E[i].to;
if(!vis[v])
{
vis[v]=1;
--all;
Q.push(v);
}
}
}
return !all;
}
int main(void)
{
int tcase,n,i,a,b,len;
scanf("%d",&tcase);
while (tcase--)
{
init();
scanf("%d",&n);
int P=0;
while (n--)
{
scanf("%s",s);
len=strlen(s);
a=s[0]-‘a‘;
b=s[len-1]-‘a‘;
if(!cur[a])
cur[a]=1,++P;
if(!cur[b])
cur[b]=1,++P;
add(a,b);
add(b,a);
++chu[a];
++ru[b];
}
int s=0;
for (i=0; i<26; ++i)
{
if(cur[i])
{
s=i;
break;
}
}
bool flag=bfs(s,P);
if(!flag)
puts("The door cannot be opened.");
else
{
vector<pii>pos;
for (i=0; i<26; ++i)
{
if((ru[i]==0&&chu[i]==0)||(ru[i]==chu[i]))
continue;
pos.push_back(pii(ru[i],chu[i]));
}
if(pos.empty())
flag=true;
else if(pos.size()>2)
flag=false;
else
{
if(pos[0].first==pos[0].second+1&&pos[1].first==pos[1].second-1)
flag=true;
else if(pos[1].first==pos[1].second+1&&pos[0].first==pos[0].second-1)
flag=true;
else
flag=false;
}
puts(flag?"Ordering is possible.":"The door cannot be opened.");
vector<int>Q;
}
}
return 0;
}
POJ 1386 Play on Words（欧拉图的判断）
原文：http://www.cnblogs.com/Blackops/p/5897527.html