SRM Div1 Easy : PerfectPermutation

問題概要：
長さNの配列Aがある
この配列は要素として０からN-1までの値がちょうど１つずつ入っている
配列Bを以下のように定義し、これを配列Aの子と呼ぶ
1. B[0] = 0
2. B[i] = A[B[i-1]] ( 1 <= i <= N-1 )
配列Bの要素が0からN-1までをちょうど１つずつ持つ時、AとBはperfectである

長さNの配列Pが与えられる
子と自分の関係がperfectであるような長さNの配列Qを求めよ
この配列QはPとの差が最小でなければならない
差とは、P[i]!=Q[i](0<=i<=N-1)となるようなiの数である
この差の最小値をリターンせよ

解法：
配列のサイクルをDFS or Union-Findで数える
サイクルとは、例えば{2,3,0,1}という配列が与えられた時、
{2,0} と {3,1}がサイクルである
{4,2,6,0,3,5,9,7,8,1}という配列が与えられた時、
{4,3,0},{2,6,9,1},{5},{7},{8}がサイクルである
サイクルが１つしかない場合、既に条件を満たしているので答えは０となる
それ意外の場合はサイクルの数が答えとなる
２つのサイクルを１つにまとめることを考える
片方のサイクルから任意の要素を１つと、もう片方のサイクルから任意の要素を１つ選びスワップする
すると、スワップされた要素の次の行き先はスワップ前のサイクルなので、２つのサイクルが１つにまとまる
こうして分けたサイクルからそれぞれ要素をどれでも良いので１つ選び自分の属するサイクルとは別のサイクルに置く事でそれぞれのサイクルを１つにまとめることができるため、それが配列Qとなる

コード：

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

typedef long long ll;
const int IINF = INT_MAX;

int par[100];

int find(int x){
  if( par[x] == x ) return x;
  return par[x] = find(par[x]);
}

inline void unit(int x,int y){
  x = find(x), y = find(y);
  if( x != y ) par[x] = par[y];
}

class PerfectPermutation {
public:

  int reorder( vector <int> P ) {
    int len = P.size();
    rep(i,len) par[i] = i;
    rep(i,len) unit(P[i],P[P[i]]);
    set<int> S;
    rep(i,len) S.insert(find(i));
    if( (int)S.size() == 1 ) return 0;
    return (int)S.size();
  }
};