HDU 1689 Alien's Necklace：BFS 求最小奇數環

題目大意

無向圖，求長度 ≥ 3 且為奇數的最小環。若不存在輸出 Poor JYY.，否則輸出環長。

核心難點

普通 BFS 用一維 vis[] 只能判斷是否訪問，無法區分「偶數步到達」與「奇數步到達」。本題要求環長為奇數，需記錄到達步數奇偶性。

解法：二維訪問標記 BFS

• vis[u][0]：節點 u 在偶數長度路徑中出現過。
• vis[u][1]：節點 u 在奇數長度路徑中出現過。
• 從每個節點 s 作為起點 BFS：
  dis[s] = 1（視為長度 1），vis[s][1] = 1。
  展開邊 (v, to)：
    dis[to] = dis[v] + 1。
    若 to == s 且 dis[v] ≥ 3 且 dis[v] 為奇數 → 找到奇環，返回 dis[v]。
    若 vis[to][dis[to]%2] 已標記 → 剪枝繼續。
    否則標記並入隊。
• 對每個節點跑一次 BFS，取全局最小值。

完整代碼（C++）

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1010, INF = 0x3f3f3f3f;
vector G[MAXN];
int vis[MAXN][2], dis[MAXN];
int n, m;

int bfs(int s) {
    memset(vis, 0, sizeof vis);
    queue q;
    q.push(s);
    dis[s] = 1; vis[s][1] = 1;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : G[u]) {
            dis[v] = dis[u] + 1;
            if (v == s && dis[u] >= 3 && (dis[u] % 2 == 1))
                return dis[u];
            if (vis[v][dis[v] % 2]) continue;
            vis[v][dis[v] % 2] = 1;
            q.push(v);
        }
    }
    return INF;
}
int main() {
    int T; scanf("%d", &T);
    for (int cs = 1; cs <= T; ++cs) {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; ++i) G[i].clear();
        for (int i = 0, u, v; i < m; ++i) {
            scanf("%d%d", &u, &v);
            G[u].push_back(v);
            G[v].push_back(u);
        }
        int ans = INF;
        for (int i = 1; i <= n; ++i) ans = min(ans, bfs(i));
        if (ans != INF)
            printf("Case %d: JYY has to use %d balls.\n", cs, ans);
        else
            printf("Case %d: Poor JYY.\n", cs);
    }
    return 0;
}

複雜度

• 時間：O(n (n+m))，n ≤ 1000 可接受。
• 空間：O(n+m)。

關鍵點總結

1. 二維 vis 區分奇偶步數，避免錯過奇環或誤判偶環。
2. 起點初始 dis=1 保證返回時 dis[u] 即為環長（含起點兩次）。
3. 剪枝條件 vis[v][dis[v]%2] 保證同一奇偶性不重複入隊，正確性源於 BFS 層次性質。