Drolca

Apologize To Drolca
随笔 - 28, 文章 - 1, 评论 - 6, 引用 - 0
数据加载中……

pku 1386 Play on Words 欧拉回路

#include <iostream>
using namespace std;
const int maxn=1005;
const int M=28;
int map[M][M];
int chu[M],ru[M];
bool vis[M];        
int n;
int sum;

void dfs(int s)
{
    vis[s]
=true;
    sum
++;
    
int i;
    
for(i=0;i<26;i++)
        
if(map[s][i]&&!vis[i])
            dfs(i);
}


int main()
{
    
int T;
    scanf(
"%d",&T);
    
while(T--)
    
{
        memset(map,
0,sizeof(map));
        memset(chu,
0,sizeof(chu));
        memset(ru,
0,sizeof(ru));
        memset(vis,
0,sizeof(vis));

        scanf(
"%d",&n);
        
int i;
        
for(i=0;i<n;i++)
        
{
            
char word[maxn];
            scanf(
"%s",&word);
            
int len=strlen(word);
            map[word[
0]-'a'][word[len-1]-'a']=1;
            chu[word[
0]-'a']++;
            ru[word[len
-1]-'a']++;
        }

        
int n0=0,n1=0,n2=0,n3=0;
        
int s=-1,e=-1;
        
for(i=0;i<26;i++)
        
{
            
            
if(chu[i]==0&&ru[i]==0)
                
continue;
            n0
++;
            
if((ru[i]-chu[i])==1)
                n2
++;
            
if((chu[i]-ru[i])==0)
                n3
++;
            
if((chu[i]-ru[i])==1)
            
{
                s
=i;
                n1
++;    
            }

            e
=i;
        }

        sum
=0;
        
if(s!=-1)
            dfs(s);
        
else
            dfs(e);
        
if(sum!=n0)
        
{
            printf(
"The door cannot be opened.\n");
            
continue;
        }

        
if( (n1==1&&n2==1&&n3==(n0-2)) || (n0==n3) )
            printf(
"Ordering is possible.\n");
        
else
            printf(
"The door cannot be opened.\n");
    }

    
return 0;
}

posted on 2009-09-18 12:36 Drolca 阅读(248) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理