概要
問題文 → ■ ■
公式解説 → なさそう？？
自分の提出 → ■
完全マッチングの一意性という、難しそうな条件が与えられています。
手段は限られていそうで「簡単に解けるならばきっとこういうことが成り立つだろう」とでも予想できればそのまま解けてしまうような問題。ちゃんと証明せず解けてしまう人も割と居ると思います。
調べても証明を記述している方が見当たらなかったので、書いておきます。
補題
細かいところを無視すれば、おおよそ次の問題です。
$2$ 部グラフ $G=(V,E)$ （$V = A\amalg B$ で全ての辺は $AB$ 間を結ぶ）がある。$G$ は唯一の完全マッチング $M$ を持つことが分かっている。$M$ を復元せよ。
完全マッチングの一意性から、次を示すことができます。
【補題】二部グラフ $G=(A\amalg B,E)$ が唯一の完全マッチングを持ち、$|A| = |B|\geq 1$ であるとき，$\deg(a) = 1$ となる $a \in A$ が存在する。
証明
任意の $a\in A$ が $\deg a \geq 2$ を満たすと仮定します。次のように長さ無限大の歩道 $W = a_1b_1a_2b_2\cdots$ をとります。
- $a_1\in A$ を適当にとる（$|A| \geq 1$ より可能）
- $a_i$ までとったとき、$a_ib_i\notin M$ となる $b_i\in B$ をとる（$\deg a_i\geq 2$ より可能）
- $b_i$ までとったとき、$b_ia_{i+1}\in M$ となる $a_{i+1}\in A$ をとる（$M$ が完全マッチングなので一意存在）
$W$ は「交互歩道」つまり、$M$ に属する辺とそうでない辺を交互に用いています。$W$ は（有限グラフ上の）長さ無限大の歩道なので、サイクルを含みます。それをひとつとり、$C$ とします。
$G$ は二部グラフで、$C$ の長さは偶数です。
また、$C$ は $M$ に属する辺とそうでない辺を交互に用いています。したがって、$C$ 上の辺について $M$ に属するかどうかを入れ替えることで、新しい完全マッチング $M’$ が得られます。$G$ 上の完全マッチングの一意性に矛盾するので証明できました。
問題の解法
上記の補題より次数 $1$ の点の存在が保証されます。この点のマッチング相手は決まる。これらの $2$ 頂点を除いたグラフて再帰的に同じ問題を解けばよいです。
次数 $1$ の頂点の検出を、累積和などを用いて高速化する必要があります。
