競技プログラミング用 知識集積所
ABC436E - Minimum Swap
最終更新：
sport_programming
-
view
問題
必要知識
B以下レベルの内容は省略
考え方
まず、最短手数が何手で、それがどういう内容であるかを考えてみる。
「本来位置Xにいるべきものが位置Yにいる」ということをX→Yの辺で表現すると、間違った位置にいる頂点の中での巡回がいくつかできる。
（正しい位置にいるものは長さ1の巡回を考えるなら、全頂点の中でいくつかの巡回ができる）
各巡回の「長さ-1」を合計した値を考えると、1回の操作でこの合計は最大でも1しか減らせない。
逆に、同じ巡回の中での入れ替えをすると、必ずこの値は1減る。
（正しい位置にいるものは長さ1の巡回を考えるなら、全頂点の中でいくつかの巡回ができる）
各巡回の「長さ-1」を合計した値を考えると、1回の操作でこの合計は最大でも1しか減らせない。
逆に、同じ巡回の中での入れ替えをすると、必ずこの値は1減る。
つまり、「同じ巡回の中での入れ替え」のみで手順を実行することが、最短手順で終わることの必要十分条件である。
したがって、1手目は、同じグループ内から2つ選ぶパターン数を求めればよい。
したがって、1手目は、同じグループ内から2つ選ぶパターン数を求めればよい。
それを実現する方法はいくつかあるが、UnionFind木※を使って各連結成分ごとに処理するのが最も楽だと思われる。
解答例
注意点
解答にはlong long型を用いる。
全部つながる巡回ができる場合、N(N-1)/2通りが答えになり、int型からはみ出てしまう。
