POJ 2513 Colored Sticks：歐拉通路 + 並查集 + 字典樹判斷木棍能否首尾相連

問題建模

每根木棍兩端有顏色，視為無向圖的邊；顏色視為頂點。問題轉化為：給定無向圖，是否存在歐拉通路（恰好走過每條邊一次，可不回到起點）。

歐拉通路存在條件（無向圖）

1. 連通性：所有度數 > 0 的頂點屬於同一連通分量。
2. 奇度數頂點數：為 0（歐拉迴路）或 2（歐拉通路，起點終點不同）。

資料結構協作

• 字典樹：將顏色字串（小寫字母，長 ≤ 10）映射為整數 ID（1~V），支援快速插入與查找。
• 並查集：維護頂點連通性，讀入邊時即時合併。
• 度數陣列：統計各頂點度數。

演算法流程

1. 初始化字典樹、並查集、度數陣列。
2. 讀入每對顏色 (a, b)：
    透過字典樹獲取/分配 ID u, v。
    deg[u]++, deg[v]++。
    並查集合併 u, v。
    記錄邊 (u, v)。
3. 檢查條件：
    計算奇度數頂點數 odd，若 odd > 2 → Impossible。
    檢查連通性：所有有度數的頂點是否同一並查集根。
    （實作技巧：用邊列表二次遍歷並查集，計算連通分量數）。
4. 輸出 Possible 或 Impossible。

完整 C++ 實作

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

const int MAXN = 500005;  // 最大節點數：邊數×2
const int SIGMA = 26;

struct Trie {
    int sz;
    int g[MAXN][SIGMA];
    int val[MAXN];  // 節點對應的頂點 ID（0 表未分配）
    void init() {
        sz = 1; val[0] = 0;
        memset(g[0], 0, sizeof(g[0]));
    }
    int idx(char ch) { return ch - 'a'; }
    int insert(const char* s) {
        int u = 0, n = strlen(s);
        for (int i = 0; i < n; ++i) {
            int v = idx(s[i]);
            if (!g[u][v]) {
                g[u][v] = sz;
                memset(g[sz], 0, sizeof(g[sz]));
                val[sz++] = 0;
            }
            u = g[u][v];
        }
        if (!val[u]) {           // 首次出現，分配新 ID
            val[u] = ++N;
            fa[N] = N;
            deg[N] = 0;
        }
        return val[u];
    }
} T;

int N, E;
int fa[MAXN], deg[MAXN];
pair edges[MAXN];

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

bool check() {
    // 1. 奇度數檢查
    int odd = 0;
    for (int i = 1; i <= N; ++i) if (deg[i] & 1) ++odd;
    if (odd > 2) return false;

    // 2. 連通性檢查：用邊列表二次合併並查集
    int comp = N;
    for (int i = 0; i < E; ++i) {
        int u = findFa(edges[i].first);
        int v = findFa(edges[i].second);
        if (u != v) { fa[u] = v; --comp; }
    }
    return comp <= 1;  // 所有有邊頂點在同一分量
}

int main() {
    T.init();
    N = E = 0;
    char a[11], b[11];
    while (scanf("%s%s", a, b) == 2) {
        int u = T.insert(a);
        int v = T.insert(b);
        ++deg[u]; ++deg[v];
        edges[E++] = {u, v};
    }
    puts(check() ? "Possible" : "Impossible");
    return 0;
}

關鍵實作細節

• 字典樹節點數上限：每條邊 2 個顏色，每顏色長 ≤ 10，最多 20 萬字元，MAXN = 500005 足夠。
• 並查集路徑壓縮：findFa 遞歸寫法簡潔高效。
• 連通性判斷技巧：不需額外 DFS，直接利用邊列表對並查集再合併一次，最後數根節點個數（排除孤立點）。
• 輸入結束：scanf("%s%s") == 2 自動處理 EOF。

複雜度分析

設 V 為顏色種類數，E 為木棍數。
• 字典樹插入：O(E × L)，L ≤ 10。
• 並查集操作：O(E α(V))。
• 總時間 O(E)，空間 O(V + E)，極高效率。