ACM/ICPC 之 DFS求解欧拉通路路径（POJ2337）

　　判断是欧拉通路后，DFS简单剪枝求解字典序最小的欧拉通路路径

//Time:16Ms     Memory:228K

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

using namespace std;

#define MAX 1005

#define MAXS 24 //姓名

#define MAXN 26 //字母

struct Edge{

    char name[MAXS];

    int a,b;

    friend bool operator < (Edge &e1, Edge &e2)

    { return strcmp(e1.name, e2.name) < 0; }

}e[MAX];

int n;

int in[MAXN], out[MAXN];    //入度与出度

int order[MAX];     //顺序路径

bool v[MAX];

bool dfs(int x, int rk)

{

    if(rk == n) return true;

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

    {

        if(!v[i] && x == e[i].a){

            v[i] = true;

            order[rk] = i;

            if(dfs(e[i].b, rk+1)) return true;

            v[i] = false;

        }

    }

    return false;

}

int main()

{

    //freopen("in.txt","r",stdin);

    int T;

    scanf("%d",&T);

    while(T--){

        memset(e,0,sizeof(e));

        memset(in,0,sizeof(in));

        memset(out,0,sizeof(out));

        memset(order,-1,sizeof(order));

        memset(v,false,sizeof(v));

        scanf("%d",&n);

        //构图

        int st = 26;    //st:起点

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

        {

            scanf("%s",e[i].name);

            e[i].a = e[i].name[0] - 'a';

            e[i].b = e[i].name[strlen(e[i].name) - 1] - 'a';

            out[e[i].a]++;

            in[e[i].b]++;

            if(e[i].a < st) st = e[i].a;

        }

        sort(e,e+n);

        //欧拉路判定

        int odd = 0;    //奇度结点个数

        bool flag = true;

        for(int i = 0 ; i < MAXN; i++)

        {

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

            {

                odd++;

                if(out[i] - in[i] == 1)

                    st = i;

                else if(out[i] - in[i] != -1)

                {

                    flag = false;

                    break;

                }

            }

        }

        if(flag && (odd ==2 || odd == 0) && dfs(st,0))  //满足欧拉通路(排除非连通)+完整路径(判断非连通)

        {

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

                printf("%s.", e[order[i]].name);

            printf("%s\n", e[order[n-1]].name);

        }

        else printf("***\n");

    }

    return 0;

}