POJ 1182: 食物链

問題
http://poj.org/problem?id=1182

概要
動物がN匹いて、1..Nの番号が振られている。
動物はA,B,Cの3種に分けられ、A->B->C->Aの強弱関係。
次の2種類の情報が順番にk個与えられる。

1. xはy同じ種類
2. xはyを食べる

逐次処理したとき矛盾する情報はいくつ出てくるか。
ただし矛盾した情報はその場で捨て、以降考慮しないで良い。

解法・感想
アリ本p85より。Union-Find木を使います。
A,B,C用の配列を作ったらダメだし...と明後日の方向を見つめていた為、init(N*3)に目から鱗でした。
ただ、感動した割にpar[MAX_N*3]としないで弾かれるあたりが限界です。
最大入力数が10万と大きいため、cinを使うと弾かれます。

ソースコード

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <functional>
#include <algorithm>
#define MAX_N 50001
#define MAX_K 100001
#define DBG 0
using namespace std;
int par[MAX_N*3];
int rank[MAX_N*3];
int N,K;
int T[MAX_K],X[MAX_K],Y[MAX_K];

// n要素で初期化
void init(int n){
  for(int i = 0; i < n; i++){
 par[i] = i;
 rank[i] = 0;
  }
}

//木の根を求める
int find(int x){
  if(par[x] == x){
 return x;
  }
  else{
 return par[x] = find(par[x]);
  }
}

//xとyの属する集合を併合
void unite(int x, int y){
  x = find(x);
  y = find(y);
  if(x==y){
 return ;
  }
  
  if (rank[x] < rank[y]){
 par[x] = y;
  }
  else{
 par[y] = x;
 if(rank[x] == rank[y]){
   rank[x] += 1;
 }
  }
}  
// xとyが同じ集合に属するか否か
bool same(int x, int y){
  return find(x) == find(y);
}

void solve(){
  init(N*3);
  
  int ans = 0;
  for(int i = 0; i < K; i++){
 int t = T[i];
 int x = X[i] - 1, y = Y[i] - 1;
 if(x < 0 || N <= x || y < 0 || N <= y){
   ans += 1;
   if(DBG){
  cout << i << endl;
   }
   continue;
 }
 
 if(t == 1){
   if(same(x, y+N) || same(x, y+2*N)){
  ans += 1;
  if(DBG){
    cout << i << endl;
  }
   }
   else{
  unite(x, y);
  unite(x+N, y+N);
  unite(x+2*N, y+2*N);
   }
 }
 else{
   if(same(x, y) || same(x, y+2*N)){
  ans += 1;
  if(DBG){
    cout << i << endl;
  }
   }
   else{
  unite(x, y+N);
  unite(x+N, y+2*N);
  unite(x+2*N, y);
   }
 }
  }
  cout << ans << endl;
}

int main(){
  cin >> N >> K;
  for(int i = 0; i < K; i++){
 scanf("%d %d %d", &T[i], &X[i], &Y[i]);
  }
  solve();
  return 0;
}