Day 134-Q2 | 二部被覆グラフによる最短奇閉路検出

問題

$N$頂点$M$辺の無向単純グラフが与えられる。このグラフに含まれる閉路のうち、辺数が奇数であるものの最小の長さ（辺数）を求めよ。奇閉路が存在しない場合（グラフが二部グラフの場合）は-1を出力せよ。

入力形式

N M
u_1 v_1
u_2 v_2
...
u_M v_M

制約

$2 \le N \le 1000$

$0 \le M \le 2000$

$1 \le u_i,v_i \le N$、$u_i\neq v_i$

多重辺なし

入出力例

入力例1

出力例1

頂点$1,6,7$が長さ3の奇閉路。$1$–$2$–$3$–$4$–$5$–$1$は長さ5の奇閉路だが、より短い長さ3の閉路が存在するため答えは3。

入力例2

出力例2

-1

6頂点の単純サイクルは偶数長で二部グラフ。奇閉路は存在しない。

概念図

ヒント（段階的開示）

ヒント1（方向性）

BFSで二部彩色すると矛盾する辺が見つかった時点で二部でないことは分かるが、それが最短閉路とは限らない。「パリティの矛盾」を通常のグラフ探索の枠を超えて距離として直接測れるよう、グラフ自体を作り替えることを考えよ。

ヒント2（アプローチ）

各頂点$v$を「$(v,0)$」と「$(v,1)$」の2つに分身させ、元の辺$(u,v)$を$(u,0)$–$(v,1)$と$(u,1)$–$(v,0)$の2本に張り替えたグラフ（頂点数$2N$）を作る。この上で$(v,0)$から$(v,1)$への最短距離は「$v$を通る最短の奇閉路長」に一致する。全頂点について求め最小値を取る。

ヒント3（誘導）

from collections import deque

def shortest_odd_cycle(n, edges):
    adj = [[] for _ in range(2 * n)]
    for u, v in edges:
        adj[2*u].append(2*v+1); adj[2*v+1].append(2*u)
        adj[2*u+1].append(2*v); adj[2*v].append(2*u+1)
    best = None
    for v in range(n):
        dist = [-1] * (2 * n)
        dist[2*v] = 0
        dq = deque([2*v])
        while dq:
            x = dq.popleft()
            if x == 2*v+1:
                break  # 目的地に着いたら打ち切ってよい
            for y in adj[x]:
                if dist[y] == -1:
                    dist[y] = dist[x] + 1
                    dq.append(y)
        d = dist[2*v+1]
        if d != -1 and (best is None or d < best):
            best = d
    return best if best is not None else -1

制約が小さめ（$N\le1000,M\le2000$）なのは「$N$回BFS」の$O(N(N+M))$解法を意図しているため。

模範解答 (Python)

import sys
from collections import deque


def main():
    data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(data[idx]); idx += 1
    M = int(data[idx]); idx += 1
    edges = []
    for _ in range(M):
        u = int(data[idx]) - 1; idx += 1
        v = int(data[idx]) - 1; idx += 1
        edges.append((u, v))

    adj = [[] for _ in range(2 * N)]
    for u, v in edges:
        adj[2 * u].append(2 * v + 1)
        adj[2 * v + 1].append(2 * u)
        adj[2 * u + 1].append(2 * v)
        adj[2 * v].append(2 * u + 1)

    best = None
    for v in range(N):
        dist = [-1] * (2 * N)
        dist[2 * v] = 0
        dq = deque([2 * v])
        target = 2 * v + 1
        while dq:
            x = dq.popleft()
            if x == target:
                break
            for y in adj[x]:
                if dist[y] == -1:
                    dist[y] = dist[x] + 1
                    dq.append(y)
        d = dist[target]
        if d != -1 and (best is None or d < best):
            best = d

    print(best if best is not None else -1)


main()

Step-by-Step 解説

1なぜパリティを空間に埋め込むのか
「同じ頂点に戻る」「歩数が奇数」を同時に満たすパスは通常のBFSの状態表現では扱えない。「頂点×パリティ」を新しいノードとする。

2二部被覆グラフの構築
辺を渡るたびパリティが反転するよう$(u,0)$–$(v,1)$、$(u,1)$–$(v,0)$を張る（無向なので双方向）。

3$(v,0)$–$(v,1)$間の最短距離=最短奇閉路
最短距離で得られる歩道は単純閉路になっている。全頂点について求め最小を取る。

4早期打ち切り
目的ノードをキューから取り出した時点でbreakしてよく、実測でも大きな高速化になる。

5計算量
1回$O(N+M)$のBFSを$N$回、全体で$O(N(N+M))$。制約内なら十分高速。

よくあるミス

ミス	原因	正しい書き方
被覆辺を$(u,0)$–$(v,0)$のようにパリティ保存で張る	パリティ反転が本質であることを見落とす	必ず$(u,0)$–$(v,1)$、$(u,1)$–$(v,0)$の組み合わせで張る
1頂点だけBFSして答えとする	最短奇閉路がどこにあるか分からないことを忘れる	全頂点$v$について調べ最小値を取る
二部グラフのとき-1を出し忘れる	`dist[target]`が-1のままなのを見落とす	`best is None`なら-1を出力
$N$が大きい前提でTLEを心配しすぎる	一般に大規模な最短奇閉路検出は非自明と混同	本問の制約（$N\le1000$）では素直な$O(N(N+M))$で十分

次のステップ

発展: 辺に正の重みが付いた場合の最短奇閉路（重み和最小）をBFSをダイクストラに置き換えて求めよ。
発展2: $N$が$10^5$規模でも高速に最短奇閉路を求める方法を調べ、本問の素朴な解法との違いを整理せよ。
次回予告: 次回のテーマは今後のセッションで選定

自己評価

完全理解おおむね理解要復習

Day 134-Q2 — 二部被覆グラフ（Bipartite Double Cover）による最短奇閉路検出

問題