毎日一回コード書く

今回はものすごくサボリぎみだけど。

int par[MAX_N];
int rank[MAX_N];

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

//xとyが同じ集合に属するか否か
bool same(int x, int y){
  return find(x) == find(y);
}

蟻本よりUnion-Find木の実装。 1時間以内で終わらそうと思ったけど写すだけなんで5分で終わったでござるの巻。5分でも掛かりすぎだけど。
「これクラスで実装できんじゃね？」って思って作ったのがこちら。

class uftree{

private:
  int par[MAX_N];
  int rank[MAX_N];

public:
  void init(int);
  void unite(int, int);
  int find(int);
  bool same(int, int);
 
};

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

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

//xとyの属する集合を併合
void uftree::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]++;
    }
  }
}

//xとyが同じ集合に属するか否か
bool uftree::same(int x, int y){
  return find(x) == find(y);
}

コンパイルは通ったけど動くかどうかは知らない。クラス化しただけだから多分動くと思うけど。
というわけで、一日一回コード書くという習慣の一日目、何の工夫もないただの書き取りでした。