AOJ 1016 Fibonacci Sets

問題

Fibonacci Sets

f(i) = f(i-1) + f(i-2)

フィボナッチ数です。で、1001で割って。 i...Vのノードがあって、iとjが

| F(i) - F(j) | < d

ならiとjは同じ集団に属している。 集団の数はいくつか

解法

Union_Find木を使うと解けます。 蟻本の出番。

コード

int par[N], rank[N];

void init(int n){
  rep(i, n){
    par[i] = i;
    rank[i] = 0;
  }
}

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

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]++;
  }
}

bool same(int x, int y){
  return find(x) == find(y);
}

int V, d;
int f[N];
int main(){
  f[0] = 1; f[1] = 2;
  REP(i, 2, N) f[i] = (f[i-1] + f[i-2])%1001;

  while(~scanf("%d%d", &V, &d)){
    init(V+1);
    REP(i, 1, V+1){
      REP(j, i+1, V+1){
    if(abs(f[j]-f[i]) < d) unite(i, j);
      }
    }
  int res = 0;
  REP(i, 1, V+1) if(par[i] ==  i) res++;
  printf("%d\n", res);
  }
  return 0;
}