AtCoder Beginner Contest 302 G - Sort from 1 to 4
メモ
a(1~4)に動かしたいb(1~4)について有効辺を貼って得られるグラフをGとすると
この問題はＧに含まれる辺を最大個数の閉路に分ける問題になる。
このような考え方は典型で
各iについてこれをjに持っていきたいという問題設計の時に、とりあえずその通りに辺を貼ると考えやすくなることがある
(このようなN頂点N辺の有向グラフをfunctional graphと呼ぶ)
今回は、閉路の長さが短い順にとる貪欲法で解くことができる
ただ証明が難しかった（自分は未証明で解いてしまった）
簡単な証明
まず、a->b, b<-aのような周期2のものは取っていい
理由は一般のfunctional graphにおいてこの問題を解いたとき、
最終的に分けられる閉路xがa->bを含み、yがb->aを含むとすると
x, yからa->b, b->aを取り除いたうえで, x, yをマージでき、閉路の数を更新できることから、a->b, b<-aからなる周期2の閉路を取らない場合は最適解でないから
Gから周期2の閉路を取り除くと、トーナメントグラフになるが
そのグラフにおいて、必ず入次数か出次数が1になる頂点iがある
その場合iを含む閉路は必ず、その辺を通るため
その辺でiとつながってる頂点をjとしたときに、ijをマージしていい
後は同様に考えると貪欲にとっていいことが分かる。
貪欲にとっていいのは4の時の性質で、一般のfuncitonal graphでは成り立たない？
