問題
$N$ 頂点 $M$ 辺の無向グラフが与えられる（$N$は偶数とは限らない）。このグラフが完全マッチングを持つかどうかを判定せよ。
一般グラフの完全マッチング判定はEdmondsのブロッサムアルゴリズム（$O(V^3)$）で厳密に解けるが、本問ではTutte行列を使ったランダム化アルゴリズムで判定する。
Tutte行列$T$は$N\times N$の行列で、辺$(i,j)$（$i<j$）が存在すれば変数$x_{ij}$を使って$T_{ij}=x_{ij}$、$T_{ji}=-x_{ij}$とし（歪対称行列）、辺が無い場所は0とする。
定理（Tutte, 1947）: $G$が完全マッチングを持たない場合、$\det(T)$は変数の多項式として恒等的に0になる。持つ場合は恒等的に0ではない多項式になる。
変数にランダムな値を代入し、行列式が0でなければ「ほぼ確実に完全マッチングを持つ」と判定する（Schwartz-Zippel補題により誤判定確率は高々$N/p$）。
乱数生成規則: random.seed(S)実行直後から、入力で辺が与えられた順にrandom.randrange(1,p)を1回ずつ呼び出す。$p=998244353$固定。
入力形式
N M S
u_1 v_1
:
u_M v_M制約
入出力例
入力例1
4 4 42
0 1
1 2
2 3
3 0出力例1
YES入力例2
4 3 42
0 1
0 2
0 3出力例2
NO概念図
ヒント（段階的開示）
ヒント1（方向性）
完全マッチングの存在を組み合わせ的に探索するのではなく、「行列式という代数的な量に翻訳して判定する」のがこのアルゴリズムの発想である。行列式は$N!$項の符号付き和として展開されるが、その各項はグラフ上の置換に対応しており、うまく符号を打ち消し合わせる（歪対称性）ことで、完全マッチングが存在しない場合にすべての単項式が相殺されて消えてしまう（Tutteの定理）。
ヒント2（アプローチ）
行列式の各項は$N$個の頂点を1対1に結ぶ置換$\sigma$に対応する。$\sigma$をサイクル分解すると各サイクルはグラフ上の閉路に対応する。歪対称性から奇数長サイクルを含む項は必ず相殺され消える。すべてのサイクルが長さ2（辺1本の往復）である置換だけが相殺されずに残り、これがちょうど完全マッチングの集合に対応する。
ヒント3（誘導）
import random
P = 998244353
random.seed(S)
T = [[0]*n for _ in range(n)]
for (i, j) in edges: # 入力順に処理
x = random.randrange(1, P)
T[i][j] = x
T[j][i] = (-x) % P
# mod p 上のガウス消去法で行列式を計算
det = 1
for col in range(n):
ピボットを探して行swap（swapのたびにdetの符号反転）
det = (det * T[col][col]) % P
以降の行からcol列を消去
print("YES" if det != 0 else "NO")$N$が奇数の場合は特別扱い不要（歪対称行列の性質上、行列式は自動的に0になる）。
模範解答 (Python)
import sys
import random
P = 998244353
def main():
data = sys.stdin.read().split()
idx = 0
n = int(data[idx]); idx += 1
m = int(data[idx]); idx += 1
seed = int(data[idx]); idx += 1
edges = []
for _ in range(m):
u = int(data[idx]); idx += 1
v = int(data[idx]); idx += 1
if u > v:
u, v = v, u
edges.append((u, v))
random.seed(seed)
T = [[0] * n for _ in range(n)]
for (i, j) in edges:
x = random.randrange(1, P)
T[i][j] = x % P
T[j][i] = (-x) % P
def modinv(a):
return pow(a, P - 2, P)
def det_mod(mat):
sz = len(mat)
M = [row[:] for row in mat]
det = 1
for col in range(sz):
piv = None
for r in range(col, sz):
if M[r][col] % P != 0:
piv = r
break
if piv is None:
return 0
if piv != col:
M[col], M[piv] = M[piv], M[col]
det = (-det) % P
det = (det * M[col][col]) % P
inv = modinv(M[col][col])
for r in range(col + 1, sz):
if M[r][col] % P != 0:
factor = (M[r][col] * inv) % P
for c in range(col, sz):
M[r][c] = (M[r][c] - factor * M[col][c]) % P
return det % P
d = det_mod(T)
print("YES" if d != 0 else "NO")
main()Step-by-Step 解説
$T_{ij}=-T_{ji}$、対角成分0のとき、行列式は$\sum_\sigma \mathrm{sgn}(\sigma)\prod T_{i,\sigma(i)}$で定義される。積が0でないのは$\sigma$が指す辺がすべてグラフの辺に対応する場合のみ。
$\sigma$を素な巡回置換に分解すると各サイクルはグラフ上の閉路に対応する。長さ1のサイクルは対角成分0のため寄与しない。
歪対称性の下で、ある奇数長サイクルを含む置換$\sigma$について、逆向きにたどる置換$\sigma'$を考えると符号がちょうど打ち消し合い、寄与の和が0になる。これにより奇数長サイクルを含む項はすべて対消滅する。
すべてのサイクルが長さ2である置換に対応する単項式だけは、他のどの置換とも同じ単項式を生成しないため相殺されず残る。これは完全マッチングの集合そのものに対応する。
完全マッチングが存在する場合、誤って0と判定してしまう確率は高々$N/p$。存在しない場合はどんな値を代入しても必ず0で、誤って YES と判定することは絶対にない（片側誤差のモンテカルロアルゴリズム）。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| Nが奇数のとき特別扱いで即座にNOを出そうとする | 歪対称行列の性質を知らない | 実装上は何もしなくても奇数サイズの行列式は自動的に0になる |
| 乱数の消費順序を入力順以外にしてしまう | 再現性の仕様を読み飛ばす | 必ず入力で辺が与えられた順にrandomを呼ぶ |
| T[j][i]の符号を反転せず代入してしまう | 歪対称性の実装を忘れる | T[j][i] = (-x) % Pとして必ず符号を反転させる |
| ピボットが見つからない場合の扱いを誤る | ピボットが0の行を見逃す | 非零要素が見つからなければその時点でreturn 0とする |
| 誤判定確率をゼロにしようと無駄に何度も判定を回す | 過剰な安全策 | 本問の制約では1回で十分小さい誤差に抑えられる |
次のステップ
- 発展: 完全マッチングが「存在する」と判定された後、実際のマッチング（辺集合）を復元するアルゴリズムを実装せよ。
- 発展2: Edmondsのブロッサムアルゴリズムで同じグラフを解き、Tutte行列法の判定結果と厳密解が完全に一致することをランダムなテストケース多数で検証せよ。