Uva 10129 Play on Words(欧拉路)

一些秘密的门包含一个非常有趣的单词拼图。考古学家们必须解决的问题

它打开那门。因为没有其他的方式来打开大门，这个谜是非常重要的

我们。

每扇门上都有大量的磁性板。每一个盘子上都有一个字

它。板块必须以这样一种方式排列成一个序列，每一个词都以相同的方式开始

信作为前一个字结束。例如，单词“ACM”可以通过“摩托罗拉”。

你的任务是写一个计算机程序，将读的单词列表，并确定它是否

可以将所有的板按顺序排列（根据给定的规则），从而

打开门.

输入

输入由T测试用例。在输入文件的第一行上给出了它们的数目（t）。

每一个测试用例开始于一个包含一个整数N的行，该数字表示

板（1≤N≤100000）。然后正n行跟随，每一个包含一个字。每一个字

包含至少两个和至多1000个小写字符，这意味着只有字母“A”通过“Z”

出现在单词中。同一个词可能会出现在列表中的几次。

输出

您的程序必须确定是否有可能安排在一个序列中的所有板块，这样

每一个单词的第一个字母等于前一个单词的最后一个字母。所有板块从

列表必须使用，每一个完全一次。几次提到的话一定要用多少次

倍。

如果存在这样一个板块的顺序，你的程序应该打印句子的顺序是

可能。”。否则，输出的句子“门不能打开”。

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.

/*

欧拉路(填之前留下的坑).

单词中间的字母对答案是没有贡献的.

先用性质判断欧拉路连通性.

充必条件是all point度数为0 or

at most two point 度数 为奇数.

然后dfs一遍看连不连通.

*/

#include<iostream>

#include<cstdio>

#include<cstring>

#define MAXN 1001

#define MAXM 27

using namespace std;

int in[MAXM],out[MAXM],tot,n,g[MAXM][MAXM];

char s[MAXN];

bool b[MAXM],flag;

int read()

{

    int x=0,f=1;char ch=getchar();

    while(ch<'0'||ch>'9') {if(ch=='-')f=1;ch=getchar();}

    while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();

    return x*f;

}

void dfs(int u)

{

    b[u]=true;

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

      if(g[u][i]&&!b[i]) dfs(i);

     return ;

}

void Clear()

{

    tot=0;flag=false;

    memset(in,0,sizeof in);

    memset(out,0,sizeof out);

    memset(g,0,sizeof g);

    memset(b,0,sizeof b);

}

int main()

{

    int t,l;

    t=read();

    while(t--)

    {

        n=read();Clear();

        for(int i=1;i<=n;i++)

        {

            cin>>s;l=strlen(s);

            out[s[0]-96]++,in[s[l-1]-96]++;

            g[s[0]-96][s[l-1]-96]=true;

        }

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

        if(out[i]!=in[i])

        {

            if(in[i]==out[i]+1||out[i]==in[i]+1) tot++;

            else {flag=true; break; }

        }

        if(flag||tot>2)

        {

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

        }

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

            if(out[i])

            {

                dfs(i);break;

            }

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

          if(!b[i]&&(in[i]||out[i]))

            {

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

              flag=true;

              break;

            }

        if(!flag) printf("Ordering is possible.\n");

    }

    return 0;

}

巴特西

Uva 10129 Play on Words(欧拉路)

最新文章

热门文章