POJ 1776 競賽圖的哈密頓路徑構造

題目大意

給定 n (≤1000) 個任務，任意兩任務間有且僅有一條有向邊（競賽圖）。需將所有任務分成最少數量的序列，每個序列中任務間有邊相連（即形成路徑）。輸出最少序列數及具體序列。

核心定理：競賽圖必存在哈密頓路徑

數學歸納法證明：

1. n=2 顯然。
2. 假設 n=k 存在哈密頓路徑 V1→V2→...→Vk。
3. 加入 V_{k+1}，考慮其與路徑上節點的邊方向：
   • 若存在 i 使 Vi→V_{k+1} 且 V_{k+1}→V_{i+1}，插入中間得新路徑。
   • 否則，所有邊要么全指向 V_{k+1}（接在尾部），要么全從 V_{k+1} 出發（接在頭部），要么存在分界點 m 使前段指向它、後段從它出發（插在分界點）。

因此競賽圖總能構造哈密頓路徑，最少啟動次數恆為 1。

構造算法：增量插入法

維護一個鏈表表示當前哈密頓路徑。依次插入節點 k=2..n：

1. 從鏈表頭遍歷，找到第一個滿足 edge[k][i] == 1（即 k→i）的節點 i。
2. 若 i 是頭節點，將 k 作為新頭；否則插在 i 的前驅之後。
3. 若遍歷完沒找到（說明所有節點都指向 k），插在尾部。

最終鏈表即為所求哈密頓路徑，字典序最小（因插入規則保證）。

代碼實現

#include <stdio.h>
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
const int MAXN = 1010;
int nxt[MAXN], g[MAXN][MAXN];
int n;

int main() {
    while (cin >> n) {
        string line; getline(cin, line); // 吸收換行
        memset(g, 0, sizeof(g));
        for (int i = 1; i <= n; i++) {
            getline(cin, line);
            for (int j = 1; j <= n; j++)
                g[i][j] = line[(j-1)*2] - '0'; // 輸入格式：數字間有空格
        }
        memset(nxt, 0, sizeof(nxt));
        int head = 1;
        for (int k = 2; k <= n; k++) {
            bool inserted = false;
            int prev = 0;
            for (int i = head; i; i = nxt[i]) {
                if (g[k][i]) { // k -> i
                    if (i == head) head = k;
                    else nxt[prev] = k;
                    nxt[k] = i;
                    inserted = true;
                    break;
                }
                prev = i;
            }
            if (!inserted) nxt[prev] = k; // 插尾部
        }
        cout << 1 << endl << n << endl;
        for (int i = head; i; i = nxt[i]) {
            if (i != head) cout << " ";
            cout << i;
        }
        cout << endl;
    }
    return 0;
}

複雜度

插入每個節點最多遍歷當前鏈表長度，總時間 O(n^2)，n=1000 完全足夠。空間 O(n^2) 存圖。

總結

競賽圖哈密頓路徑是圖論經典結論，增量插入法構造簡單高效。本題還要求輸出字典序最小的路徑，插入規則「找第一個 k 能到達的節點插前面」天然滿足此要求。