Union-Find木

素集合のデータ構造の具体的な実装で下のスライドにわかりやすくまとめてある。

Union find(素集合データ構造)

下の実装はランク無し

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define MAX_N 10000

// union-find tree
int par[MAX_N];

void init(int n) {
    REP(i,n)
        par[i] = i;
}

int find(int x) {
    if (par[x] != x)
        par[x] = find(par[x]);
    return par[x];
}

bool same(int x, int y) {
    return find(x) == find(y);
}

void unite(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y)
        return;
    par[x] = y;
}

ランクあり

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define MAX_N 10000

// union-find tree
int par[MAX_N], rank[MAX_N];

void init(int n) {
    REP(i,n) {
        par[i] = i;
        rank[i] = 0;
    }
}

int find(int x) {
    if (par[x] != x)
        par[x] = find(par[x]);
    return par[x];
}

bool same(int x, int y) {
    return find(x) == find(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]++;
    }
}