読者です 読者をやめる 読者になる 読者になる

土下座しながら探索中

主に競技プログラミング

UVa 12755 : Easy Puzzle

UVa UnionFindTree

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

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

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

上の画像からわかるように、
本来の場所へ矢印を引くといくつかのループができる
0が含まれているループは、( ループの長さ ) - 1 回で昇順にできる
0が含まれないループは、 ( ループの長さ ) + 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;
}