\(POJ\) \(2337\) \(Catenyms\)

给出\(n\)个单词，求出最小字典序的头尾连接方案。

有向图欧拉路径 板子题。
把每个单词当做边，头字母和尾字母当做节点，建完跑 有向图欧拉路径 即可。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;

const int N = 1200, M = N * N;
int n;
int din[N], dout[N];
string s[N];

int ans[N], al;
int st[M];

// 链式前向星
int e[M], h[N], idx, w[M], ne[M];
void add(int a, int b, int c = 0) {
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

// 记录边的dfs,要注意记录边和记录点的差别
void dfs(int u) {
    for (int i = h[u]; ~i; i = ne[i]) {
        if (!st[i]) {
            st[i] = 1;
            dfs(e[i]);
            ans[++al] = w[i];
        }
    }
}

/*
【代码模板】功能：
检测有向图是否存在欧拉路径：
（1）统计每个节点的入度和出度。
（2）对于存在欧拉路径的有向图，只能有一个节点的出度比入度多1，只能有一个节点的入度比出度多1，其余节点的入度和出度必须相等。
（3）如果存在欧拉路径，这个"多余的"出度的节点将作为路径的起点，而"多余的"入度的节点将作为路径的终点。（一般不关心终点）

如何找出有向图的欧拉路径：
为了找到欧拉路径，可以从起始节点开始进行深度优先搜索，遍历所有的边。如果所有的边都被访问到，说明存在欧拉路径，否则不存在。
*/
int getStart() {
    int start = 0, a = 0, b = 0, c = 0;
    for (int i = 0; i < 26; i++) {                 // 枚举每个点,每道题的具体实现可能有差异
        if (dout[i] != din[i]) a++;                // 出度与入度不一致的数量
        if (dout[i] == din[i] + 1) b++, start = i; // 起点数量，记录起点
        if (dout[i] == din[i] - 1) c++;            // 终点数量
    }
    if (a && (b != 1 || c != 1)) return -1; // 如果有不一致的，并且不是1个，则没有欧拉路径

    // 如果是一个环，也是存在欧拉路径的，但所有点的入度和出度一致，st不会被改写，需要再手找出起点。
    // 这里不需要判断!st,因为如果st=0,则dout[st]==0,也需要继续查找
    while (!dout[start]) start++;
    return start;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("POJ2337.in", "r", stdin);
#endif
    int T;
    scanf("%d", &T);
    while (T--) {
        memset(din, 0, sizeof din);
        memset(dout, 0, sizeof dout);
        memset(h, -1, sizeof h);
        idx = 0;
        memset(st, 0, sizeof st);

        scanf("%d", &n);

        for (int i = 1; i <= n; i++) cin >> s[i]; // 第几个字符串
        sort(s + 1, s + n + 1);                   // 字典序，排序由小到大

        for (int i = n; i; i--) { // 倒序枚举，就是由大到小
            int a = s[i][0] - 'a';
            int b = s[i][s[i].size() - 1] - 'a';
            din[b]++, dout[a]++;
            add(a, b, i);
        }

        int start = getStart();
        if (start == -1) {
            printf("***\n");
            continue;
        }

        // 从start开始搜索，找出欧拉路径，是有向图的欧拉路径，不是欧拉回路
        al = 0; // 清空路径数组游标，准备开始填充路径
        dfs(start);

        if (al != n) { // 无法遍历到所有的点
            printf("***\n");
            continue;
        }

        // 控制格式输出
        for (int i = n; i > 1; i--) {
            cout << s[ans[i]];
            printf(".");
        }
        cout << s[ans[1]] << endl;
    }
    return 0;
}