题目链接：http://poj.org/problem?id=2337

题意：给定一些单词，假设一个单词的尾字母与还有一个的首字母同样则能够连接。问能否够每一个单词用一次，将全部单词连接，能够则输出字典序最小的序列。

代码：

（bin 神的板子）

#include <stdio.h>

#include <ctime>

#include <math.h>

#include <limits.h>

#include <complex>

#include <string>

#include <functional>

#include <iterator>

#include <algorithm>

#include <vector>

#include <stack>

#include <queue>

#include <set>

#include <map>

#include <list>

#include <bitset>

#include <sstream>

#include <iomanip>

#include <fstream>

#include <iostream>

#include <ctime>

#include <cmath>

#include <cstring>

#include <cstdio>

#include <time.h>

#include <ctype.h>

#include <string.h>

#include <assert.h>

using namespace std;

int t;

int n;

string s[1010];

struct Edge

{

    int to, next;

    int index;

    bool flag;

}edge[2010];

int head[300], tot;

void init()

{

    tot = 0;

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

}

void addedge(int u, int v, int index)

{

    edge[tot].to = v;

    edge[tot].next = head[u];

    edge[tot].index = index;

    edge[tot].flag = false;

    head[u] = tot++;

}

int in[250], out[250];

int cnt;

int ans[1010];

void dfs(int u)

{

    for (int i = head[u]; i != -1; i = edge[i].next)

    {

        if (!edge[i].flag)

        {

            edge[i].flag = true;

            dfs(edge[i].to);

            ans[cnt++] = edge[i].index;

        }

    }

}

int main()

{

    int t;

    cin >> t;

    while (t--)

    {

        scanf("%d",&n);

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

            cin >> s[i];

        sort(s, s + n);

        init();

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

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

        int start = 100;

        for (int i = n - 1; i >= 0; i--)

        {

            int u = s[i][0] - 'a';

            int v = s[i][s[i].length() - 1] - 'a';

            addedge(u,v,i);

            out[u]++;

            in[v]++;

            if (u < start) start = u;

            if (v < start) start = v;

        }

        int cc1 = 0, cc2 = 0;

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

        {

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

            {

                cc1++;

                start = i;

            }

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

                cc2++;

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

                cc1 = 3;

        }

        if (!((cc1 == 0 && cc2 == 0) || (cc1 == 1 && cc2 == 1)))

        {

            printf("***\n");

            continue;

        }

        cnt = 0;

        dfs(start);

        if (cnt != n)

        {

            printf("***\n");

            continue;

        }

        for (int i = n-1; i >=0 ; i--)

        {

            cout << s[ans[i]];

            if (i != 0) printf(".");

            else printf("\n");

        }

    }

    return 0;

}