実装の確認
5462 ワード
各要素を番号で表します.配列parは父親の番号を表し,par[x]=xの場合,xは所在する木の根である.
平行宇宙を集めてpoj 1703
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]++;
}
}
平行宇宙を集めてpoj 1703