Minimum Swaps to Sort

Quiz

https://practice.geeksforgeeks.org/problems/minimum-swaps/1

Submit

https://practice.geeksforgeeks.org/viewSol.php?subId=14251643&pid=700384&user=peroon

解法

f:id:peroon:20190526071618j:plain

  • 例として 2 4 5 1 3 を考える
  • N-1, つまり4回swapすれば確実にソートできる。もっと少なくできないか
  • 本当にいるべき場所に矢印を伸ばすとループが出来、グループ分けされる
  • 後はグループごとにソートすればよく、答えはΣ(ループ長 - 1)となる

使った要素

  • 色々やり方はあるだろうが、グループの管理にはUnion Findを使った
  • A[i] > Nの場合があるので配列Aは座標圧縮しておく必要があった

その他

  • 大きいテストケースを得る手段がなさそう
  • AOJ, codeforcesなら提供されている
  • AtCoderも一部提供されている