有向圖歐拉回路--try，yes，sad。。。

1.問題描述

http://www.newsmth.net/nForum/#!article/Algorithm/51895?p=1

給定N個字元串，把首尾相同的字元串連在一起（如：try --- yes --- sad ）.如果所有字元串能成串成一個環，就表明有解，否則無解，（這個環裡面必須含有所有的字元串，如果少了也是無解）。如何判斷是否有解。

2.分析

把字母當作圖中的點，把每個字元串當做一條有向邊，邊的起點是字元串首字母的點，終點是末尾字母的點。判斷是否存在一條歐拉回路即可。理論上也可以拿字元串當定點，然後try和yes之間有連接配接。不過這樣的話，字元串一多，節點就海量了。用字母的話逃不出26.複雜度相差很大啊！

輸入檔案：

try

yes

sad

dota

代碼編寫：

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

#define ARRAY_N 26

// 邊
struct enode
{
    int index;
    struct enode* next;
};

// 頂點
struct vnode
{
    char ch;
    struct enode *next;
};

struct graph
{
    struct vnode vtable[ARRAY_N];
    int num[ARRAY_N];
    int e;
    int v;
};

///
struct graph gra={{0,0},{0},0,0};

int main()
{
    char word[256];
    int len;
    while(scanf("%s", word)!=EOF)
    {
          char first=word[0];
          char last=word[strlen(word)-1];
          ++(gra.num[first-'a']);
          --(gra.num[last-'a']);
    }
    int i;
    for(i=0; i<ARRAY_N; i++)
        printf("%c - %d\n", i+'a', gra.num[i] );
    for(i=0; i<ARRAY_N; i++)
        if(gra.num[i]!=0)
        {
            printf("NO!\n");
            break;
        }
    if(i==ARRAY_N)
        printf("YES!\n");
    return 0;    
}

測試檔案：

try

yes

dota

sad

abbc

其實。。隻是用了一個26長度的整型數組而已。不需要真的去用鄰接表。但是呢，這樣其實有一個漏洞，就是集合裡面，存在兩個回路。。這樣程式也能通過。但是不符合要求。歐拉回路要求節點的出度等于入度，同時圖是連通圖！而且如果需要找出其中一條路徑的話呢？上面取巧的辦法就不能用了。