UVA 10129 Play On Words題解

problem
Some of the secret doors contain a very interesting word puzzle. The team of archaeologists has to solve it to open that doors. Because there is no other way to open the doors, the puzzle is very important for us. There is a large number of magnetic plates on every door. Every plate has one word written on it. The plates must be arranged into a sequence in such a way that every word begins with the same letter as the previous word ends. For example, the word ‘acm’ can be followed by the word ‘motorola’. Your task is to write a computer program that will read the list of words and determine whether it is possible to arrange all of the plates in a sequence (according to the given rule) and consequently to open the door.
Input
The input consists of T test cases. The number of them (T) is given on the first line of the input file. Each test case begins with a line containing a single integer number N that indicates the number of plates (1 ≤ N ≤ 100000). Then exactly N lines follow, each containing a single word. Each word contains at least two and at most 1000 lowercase characters, that means only letters ‘a’ through ‘z’ will appear in the word. The same word may appear several times in the list.
Output
Your program has to determine whether it is possible to arrange all the plates in a sequence such that the first letter of each word is equal to the last letter of the previous word. All the plates from the list must be used, each exactly once. The words mentioned several times must be used that number of times. If there exists such an ordering of plates, your program should print the sentence ‘Ordering is possible.’. Otherwise, output the sentence ‘The door cannot be opened.’
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.

中国語の意味
一連の単語を指定して、単語の先頭と末尾を接続するシーケンスを見つけることができますか?接続するルールは、前の単語の末尾文字が次の単語の先頭文字に等しく、入力した単語が重複する可能性があります
Solution

暴力DFS&& 会TLE

各単語の有効情報は実際には のみであり、

へのアクセスは不要である.
考え方1
暴力DFSの全体図、毎回DFS辺の個数が に等しいかどうかを統計します
各単語は1つのエッジで、単語の先頭と末尾の文字は2つのノードで、図を建てます

会TLE

入力は重複 && を含み、処理が面倒

考え方2
問題の核心は、各エッジを通過し、1回しか通過しない経路を見つけることであり、 では、この経路は間違いなく && であり、 が存在するかどうかを判断するだけでよい.
オーラロード&オーラリターンロード
つまり図論の と 、ウィキペディアでは簡単に紹介されています
図の種類
オーラ道路
オーラかいろ
むきず
2つの奇数ノードのみを含む
奇数ノードを含まない
有向図
ベースマップ連通&&最大2点出度!=入度&&一つの点入度-出度=1&&もう一つの点出度-入度=1
省略
だから二つの条件を判断するだけで、問題は解決します.

ベースチャート連通判定ベースチャート連通は、DFSまたは で

を判定することができる.

ノードの度数は上記条件

に適合する.
本題は明らかに方向図がある
コード#コード#

#include
#include
using namespace std;
const int maxn = 1000 +10;
int n,m;
int point[30], side[30][30],in[30],out[30]. vis[30];
bool euler();

void dfs(int);
//dfs            ，        
bool check()
{
     
    for(int i=0;i<=25;i++)
        if(point[i] )
            if(vis[i]==0)
                return false;
    return true;
}

int main()
{
     
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
     
        scanf("%d",&m);
        char buffer[maxn];
        int b;
        for(int i=1;i<=m;i++)
        {
     
            scanf("%s",buffer);
            int a=buffer[0]-'a';
            b= buffer[strlen(buffer)-1]-'a';
            point[a]=1;
            point[b] =1;
            side[a][b]=side[b][a] =1; //        ，          
            in[a]++;//    
            out[b]++;//    
        }
        dfs(b);//              ，
        if((euler() && check())|| m==1 || m==0) //       
        {
     
            printf("Ordering is possible.
");
        }
        else printf("The door cannot be opened.
");
        //      
        memset(vis,0,sizeof(vis));
        memset(side,0,sizeof(side));
        memset(point,0,sizeof(point));
        memset(in,0,sizeof(in)); 
        memset(out,0,sizeof(out)); 
    } 
    return 0; 
} 
void dfs(int now)
{
     
    vis[now]=1;
    for(int i=0;i<=25;i++)
        if(side[now][i] && !vis[i]) 
            dfs(i);
}
bool euler() //      
{
     
    int count1=0;
    int count2=0;
    for(int i=0;i<=25;i++)
    {
     
        if(in[i]-out[i]>1 && out[i] - in[i]>1)
            return false;
        if(in[i]-out[i]==1)
        {
     
            if(++count1>1) return false;
        }else if(out[i]-in[i]==1)
        {
     
            if(++count2>1)   return false;
        }
    }
    return true;
}

出力フォーマット
本題は従来のUVA出力形式とは異なり、出力ファイルの最後の行は空行でなければならない.
個人情報サイト
個人サイトYanyanの小屋へようこそ