Union-Find木使ってみた。 ARC097-D(C言語)

厳密な話は色々なサイトに書いてあるので
ゆるーい雰囲気で書きます。

まずUnion-Find木ってどこで使えるの？
AtCoderの問題だと↓がそうです。(最後に解答を載せておきます。)
D: Equals - AtCoder Regular Contest 097 | AtCoder
とにかくグループ分けしたい時に使えます。

Union-Find木の作り方
・配列を用意
全体の要素数をこえる大きさの配列を用意しましょう。

・木の根を求める(グループがどこか求める)関数を用意
再帰(ある関数の中でもう一度その関数を呼び出す)を用いて木をさかのぼって行きます。
木が伸びていくと再帰に時間がかかってしまうので再帰の時に木が短くなる時に形を変形しておきましょう。(最後にのせたコードの16行目にこの変形が書かれています。)
1→2→3→4→5(5から1にいくまで4回かかる)
1→(2,3,4,5)(5から1に1回で行ける)

・2つの要素が同じグループか判定する関数を用意
先程の関数を2つの要素について呼び出して比較します。

・グループをくっつける関数を用意
これも先程の関数を2つの要素について呼び出して等しかったら何もせず、等しくなければ片方のグループ番号をもう片方に写します。

ではARC097-Dの解答例です。

#include<stdio.h>
#include<stdbool.h>
//union find木(グループわけができる)
int par[100005];
int unifind(int n) {
	for (int i = 1; i <= n; i++) {
		par[i] = i;
	}
}
//木の根を求める
int unifind_root(int x) {
	if (par[x] == x) {
		return x;
	}
	else {
		return par[x] = unifind_root(par[x]);
	}
}
//同じグループか判定
bool unifind_same(int x, int y) {
	return unifind_root(x) == unifind_root(y);
}
//グループ併合
int unifind_unite(int x, int y) {
	x = unifind_root(x);
	y = unifind_root(y);
	if (x == y) {
		return 0;
	}
	par[x] = y;
}
int main() {
	int p[100005] = {};
	int q[100005] = {};
	int result = 0;
	int xy[100005][2] = {};
	int m;
	int n;
	scanf("%d%d", &n,&m);
  	unifind(n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &p[i]);
		q[p[i]] = i;
             //qはその値が左から何番目にあるかを示す配列
	}
	for (int i = 1; i <= m; i++) {
		scanf("%d%d", &xy[i][0], &xy[i][1]);
		 unifind_unite(xy[i][0] , xy[i][1]);
	}
	for (int i = 1; i <= n; i++) {
              //左からi番目の数が所属するグループと数字iが所属するグループが等しければ良い
		if (unifind_same(i, q[i])) {
			result++;
		}
	}
	printf("%d", result);
}