有向图欧拉回路--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长度的整型数组而已。不需要真的去用邻接表。但是呢，这样其实有一个漏洞，就是集合里面，存在两个回路。。这样程序也能通过。但是不符合要求。欧拉回路要求节点的出度等于入度，同时图是连通图！而且如果需要找出其中一条路径的话呢？上面取巧的办法就不能用了。