読者です 読者をやめる 読者になる 読者になる

プロコン初心者日記

解いたプロコンの問題を保存しておくためのブログ

【自分用メモ】Union-Find木

Union-Find木のコード

参考書

プログラミングコンテストチャレンジブック [第2版]

Union-Find木とは…
・グループ分けを管理するデータ構造
・根が同じ場合同じグループとする

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
using namespace std;

#define ll         long long
#define PI         acos(-1.0)
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)

#define MAX_V ノードの数

int par[MAX_V]; //ノードiの親=par[i]
int rnk[MAX_V]; //深さ

//配列の初期化
//最初は自分が根
void init(int V){
    FOR(i, 0, V){
        par[i] = i;
        rnk[i] = 0;
    }
}

//根を探す
int find(int x){
    if(par[x] == x) return x;
    return par[x] = find(par[x]);
}

//合併
void unite(int x, int y){
    x = find(x);//xの根
    y = find(y);//yの根
    if(x == y) return;
    //深い方にくっつける
    if(rnk[x]>=rnk[y]){
        par[y] = x;
        if(rnk[x]==rnk[y]) rnk[x]++;
    }
    else{
        par[x] = y;
    }
}

//同じグループかどうか
bool same(int x, int y){
    return find(x) == find(y)
}