Set - Disjoint Set: Union Find Tree

問題

Disjoint Set: Union Find Tree | Aizu Online Judge

感想と雑多なこと

かなり更新遅くなりました... いろいろと重なっていて忙しかったり、AtCoderのD問題が解けなくて記事にできなかったりと、ここ一週間くらい自分の思うように実装できなかったですね。

現状、C問題は普通に解けるのですが、D問題が全く解けない状態です。おそらく知識が足りないのだと思います。どこかで蟻本に手を出そうかなあと思っていたのですが、その時期が近づいているなという感覚です。

今回選んだ問題は、単純に自分が知らなかった&実装経験が少ない、グラフ構造（木）に関する問題です。

考え

P[i]をiの親要素であると定義し、あとは木での知識を用いれば良い。

Accepted Program

#include <iostream>
using namespace std;

int P[10001];

// initialize
void init (int n) {
  // P[i] means the parent of 'i'.
  for (int i = 0; i <= n; i++) {
    P[i] = i;  
  }    
}
// check the root of 'x'
int root (int x) {
  if (P[x] == x) {
    return x;  
  }  
  else {
    return root (P[x]);  
  }
}
// unite both root of 'x' and 'y'
void unite (int x, int y) {
  P[root(x)] = root(y);    
}
int sames (int x, int y) {
  if (root(x) == root(y)) {
    return 1;  
  }  
  else {
    return 0;  
  }
}

int main () {
  int n, m;
  cin >> n >> m;
  init(n);
  for (int i = 0; i < m; i++) {
    int c, x, y;
    cin >> c >> x >> y;
    if (c == 1) {
      cout << sames(x, y) << endl;  
    }       
    else {
      unite(x, y);  
    }
  }
}