POJ 2337 Catenyms：有向圖歐拉路徑與字典序最小

題目大意

給定 n (3≤n≤1000) 個單詞，每個單詞視為一條有向邊：從首字母指向尾字母。求一條經過所有邊恰好一次的路徑（歐拉路徑），並使拼接後的單詞序列字典序最小。不存在輸出 "***"。

解題步驟

1. 建圖：26 個字母作節點，單詞作邊。記錄入度、出度，並查集維護連通性。
2. 字典序排序：對邊按單詞字典序升序排列，確保 DFS 時優先選擇字典序小的邊。
3. 判定歐拉路徑存在性：
   • 所有有邊節點屬於同一連通分量（並查集）。
   • 要么所有節點入度=出度（歐拉回路），要么恰有一個節點出度=入度+1（起點），一個節點入度=出度+1（終點），其餘相等。
4. 確定起點：
   • 若有出度>入度的節點，作為起點。
   • 否則（歐拉回路），選字典序最小的有邊節點作為起點。
5. Hierholzer 算法 DFS 構造路徑：從起點出發，按字典序遞歸遍歷未用邊，回溯時記錄邊編號，反序即為路徑。

代碼實現

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
using namespace std;

struct Edge { int u, v; string word; } edges[1100];
bool used[1100];
int in[27], out[27], fa[27], path[1100], top;
bool has[27];

int find(int x) { return fa[x] ? fa[x]=find(fa[x]) : x; }

bool checkEuler() {
    // 連通性
    int root = 0;
    for (int i = 1; i <= 26; i++) if (has[i]) {
        if (!root) root = find(i);
        else if (find(i) != root) return false;
    }
    // 度數條件
    int start = 0, cnt = 0;
    for (int i = 1; i <= 26; i++) if (has[i]) {
        if (in[i] != out[i]) {
            if (abs(in[i] - out[i]) > 1) return false;
            cnt++;
            if (out[i] > in[i]) start = i;
        }
    }
    if (cnt == 0) { // 回路，選最小字母作為起點
        for (int i = 1; i <= 26; i++) if (has[i]) { start = i; break; }
    } else if (cnt != 2) return false;
    // 將 start 存入全局變量供 DFS 使用
    return true;
}

void dfs(int u) {
    for (int i = 1; i <= n; i++) if (!used[i] && edges[i].u == u) {
        used[i] = true;
        dfs(edges[i].v);
        path[++top] = i;
    }
}

int main() {
    int T; cin >> T;
    while (T--) {
        cin >> n;
        memset(in, 0, sizeof(in));
        memset(out, 0, sizeof(out));
        memset(fa, 0, sizeof(fa));
        memset(has, 0, sizeof(has));
        for (int i = 1; i <= n; i++) {
            cin >> edges[i].word;
            edges[i].u = edges[i].word[0] - 'a' + 1;
            edges[i].v = edges[i].word.back() - 'a' + 1;
            has[edges[i].u] = has[edges[i].v] = true;
            int fu = find(edges[i].u), fv = find(edges[i].v);
            if (fu != fv) fa[fu] = fv;
            out[edges[i].u]++; in[edges[i].v]++;
        }
        sort(edges+1, edges+n+1, [](const Edge& a, const Edge& b){ return a.word < b.word; });
        if (!checkEuler()) { puts("***"); continue; }
        top = 0; memset(used, 0, sizeof(used));
        dfs(start);
        for (int i = top; i >= 2; i--) cout << edges[path[i]].word << '.';
        cout << edges[path[1]].word << endl;
    }
    return 0;
}

關鍵點

1. 邊按單詞字典序排序，DFS 自然產生字典序最小的歐拉路徑。
2. 並查集檢查連通性（僅考慮有邊節點）。
3. Hierholzer 算法：遞歸遍歷邊，回溯時記錄，反序輸出。
4. 起點選擇：優先出度>入度的點；否則選最小字母（保證回路字典序最小）。