面白い問題おしえて～な 28問目

面白い問題おしえて～ ..

368:１３２人目の素数さん
18/11/18 02:36:13.22 ZJOO9Eig.net
>>346
スレ汚しすまん。まだ間違ってる。
挿げ替えのアルゴリズムは >>344では不十分。
以外に訂正。
とりあえず、全ブロックの→を挿げ替えで同一成分にする。
これで十分。
もしこれで2成分以上あったとする。
しかし元のグラフは連結なので2成分X YとXの通過する点とＹの通過する点を結ぶ→がみつかる。
実際異なる連結成分を結ぶパスで長さ最小のパスを取ればそれは→である。
たとえばm=5, n=5で
X: …→02432→30243→…
Y: …→02431→10243→…
の02432と10243の様な組みである。
そしてこの部分は同一ブロックに属する。
しかし同一ブロックの→は全て同一連結成分になる様に取っているのでそれらが異なる連結成分に属するのは矛盾。

次ページ

続きを表示

1を表示