AtCoder Regular Contest 097 : D - Equals

• 問題

D - Equals

1~N の順列 p の中で (x,y) 番目のものを swap 出来るとき、最大でいくつの数をもとの位置に戻せるか、という問題。

• 解法

順列内の数を頂点、swap 出来る関係を辺として図を書いてみると、連結な部分は連結の範囲の中の任意の場所に移動可能だとわかる。あとは、順列内の数と元の場所とが同じ連結部分に属するかを調べたいので Union-Find 木 を使う。シンプル。O(NlogN)。

• 解答

Submission #2635001 - AtCoder Regular Contest 097

一発 AC だった（うれしいね）。