AOJ 1016 Fibonacci Sets

[問題文]
AIZU ONLINE JUDGE

[解法]
dp + UF木

数列を作っておいて、UF木で集合を作る。

int par[2000];
int rank[2000];
void init(int n){
  rep(i,n) par[i] = i;
  memset(rank,0,sizeof(rank));
}
int find(int x){
  if(par[x] == x) return x;
  return par[x] = find(par[x]);  
}
void unite(int x,int y){
  int root1 = find(x);
  int root2 = find(y);
  if(root1 == root2) return;
  if(rank[root1] < rank[root2]) par[root1] = root2;
  else {
    par[root2] = root1;
    if(rank[root1] == rank[root2]) rank[root1]++;
  }
}
bool same(int x,int y){
  return find(x) == find(y);
}

int dp[2000];
const int MOD = 1001;
int V,d;
int main(){
  dp[0] = 2,dp[1] = 3;
  for(int i = 2; i <= 1500; i++)
    dp[i] = (dp[i - 1]  + dp[i - 2] ) % MOD;
  while(cin>>V>>d){
    init(V);
    int memo[2000] = {0};
    for(int i = 0; i < V; i++)
      for(int j = i + 1; j < V; j++)
	if(abs(dp[i] - dp[j]) < d)
	  unite(i,j);
    set<int>ans;
    rep(i,V) ans.insert(find(i));
    cout<<ans.size()<<endl;
  }  
}