POJ 1780 Code：構造包含所有 n 位數的最短序列（歐拉迴路）

POJ 1780 Code：德布魯因序列與歐拉迴路構造

求長度為 10ⁿ + n - 1 的數字序列，使其包含所有 n 位數 (0~10ⁿ-1) 作為連續子串恰好一次。n ≤ 6。

圖論建模

• 節點：所有 n-1 位數字符串 (共 10^{n-1} 個)。
• 有向邊：從節點 u 到 v，若 u 的後 n-2 位 = v 的前 n-2 位。邊標記為 u 的最後一位 (或 v 的第一位)。共 10ⁿ 條邊，每條對應一個 n 位數。
• 每個節點出度入度均為 10 → 存在歐拉迴路。

Hierholzer 算法求歐拉迴路

• 用棧模擬遞歸 DFS：從節點 0 開始，盡可能走未訪問邊入棧；無路可走時出棧記錄路徑。
• 邊按數字 9~0 逆序添加，保證輸出字典序最小（或符合題目要求順序）。

輸出序列構造

• 路徑節點序列 stk[0..top-1]，取每個節點的最高位 (stk[i] / mod) 連接。
• 最後補上終點節點完整值 + n-1 個 0。

參考代碼 (C++)

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int maxn = 1000015;
struct Edge { int v, next; } e[maxn];
int n, mod, head[maxn], stk[maxn];
int idx, edge, top;
char vis[maxn];

void insert(int a, int b) { e[idx] = {b, head[a]}; head[a] = idx++; }

void dfs() {
    stk[top++] = 0;
    while (true) {
        int v = stk[top-1];
        if (top >= idx - (n-2)) return; // 邊已用完
        bool flag = false;
        for (int i = head[v]; i != -1; i = e[i].next)
            if (!vis[i]) { vis[i] = 1; stk[top++] = e[i].v; flag = true; break; }
        if (!flag) --top;
    }
}

int main() {
    while (scanf("%d", &n) == 1 && n) {
        if (n == 1) { puts("0123456789"); continue; }
        idx = top = 0;
        memset(head, -1, sizeof(head));
        memset(vis, 0, sizeof(vis));
        int lim = 1; for (int i=1; i= 0; j--)
                insert(i, (i%mod)*10 + j);
        dfs();
        for (int i = 0; i < top-1; i++) printf("%d", stk[i]/mod);
        printf("%d", stk[top-1]);
        for (int i = 1; i < n; i++) printf("0");
        puts("");
    }
    return 0;
}

本題是德布魯因序列構造的經典應用，展示了如何將字符串覆蓋問題轉化為圖的歐拉迴路問題並高效求解。