UVa 12755 : Easy Puzzle

問題リンク : http://uva.onlinejudge.org/external/127/12755.pdf

問題概要 :
N*Nのマスに０からN*N-1までそれぞれ１つずつかかれている
これを0から昇順になるように並び替えたい
２つのマスの値を入れ替えるためには、片方のマスが０でなければならない
昇順に並び替えるために必要なスワップの回数をこたえよ

解法 :
うまく言葉であらわせなかったので画像で

上の画像からわかるように、
本来の場所へ矢印を引くといくつかのループができる
０が含まれているループは、( ループの長さ ) - 1 回で昇順にできる
０が含まれないループは、 ( ループの長さ ) + 1 回で昇順にできる
つまり、union-findでループをまとめ
各ループについて上記の計算方法でスワップ回数をカウントしていくと良い

コード :

#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;

const int MAX_N = 300000;
int N,par[MAX_N],arr[500*500];

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

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

void compute(){

  int zero = -1;
  rep(i,N*N) if( arr[i] == 0 ) { zero = i; break; }

  vector<bool> used(N*N,false);
  rep(i,N*N) if( !used[i] ){
    used[i] = true;
    int cur = i;
    while( 1 ){
      int next = arr[cur];
      if( used[next] ) break;
      used[next] = true;
      unit(cur,next);
      cur = next;
    }
  }

  map<int,int> mp;
  rep(i,N*N) ++mp[find(i)];
  int answer = 0;
  for(map<int,int>::iterator it=mp.begin();it!=mp.end();it++){
    if( it->second == 1 ) continue;
    if( it->first == find(zero) ) answer -= 2;
    answer += it->second+1;
  }
  printf("%d\n",answer);
}

int main(){
  int T,CNT=1;
  cin >> T;
  while( T-- ){
    cin >> N;
    rep(i,N*N) cin >> arr[i], par[i] = i; 
    printf("Case %d: ",CNT++);
    compute();
  }
  return 0;
}