概要

『プログラミングコンテストでのデータ構造』で紹介されている Union-Find 木で集合を表現すると、以下のクエリを高速に実行できます。集合一つが一つの木となるため、複数の集合がある場合は全体として森になります。

ある要素 a_i と a_j が同じ集合に属しているかどうかの判定
二つの集合を一つの集合にまとめる

サンプル

POJ 1182

#include <iostream>
#include <cstdio>
using namespace std;

const int MAXN = 101024;

// Union Find >>>>>>>>>>>>>

int par[MAXN * 3]; // ノード i の属する Union Find 木におけるノード i の親
int rnk[MAXN * 3]; // ノード i の属する Union Find 木の深さ

void init(int n) { // 森の初期化 (ノード数 1 の木の集合)
    for(int i = 0; i < n; ++i) {
        par[i] = i; // ノード i のみからなる木
        rnk[i] = 0; // 深さ 0
    }
}

int find(int x) { // ノード i の属する Union Find 木の root
    if(par[x] == x) return x;
    else return par[x] = find(par[x]); // root を return しつつ、次回 find の高速化のためにノード x を直接 root につなぐ
}

bool same(int x, int y) { // クエリ1 (判定)
    return find(x) == find(y);
}

void unite(int x, int y) { // クエリ2 (二つの木をまとめる)
    x = find(x);
    y = find(y);
    if(x == y) return;
    if(rnk[x] < rnk[y]) { // root が x の木の方が root が y の木よりも低い
        par[x] = y; // root y に x の木をつなぐ
    }
    else {
        par[y] = x; // root x に y の木をつなぐ
        if(rnk[x] == rnk[y]) ++rnk[x]; // 同じ高さだったならばまとめたことによって高さ +1
    }
}

// <<<<<<<<<<<<<<< Union Find

int N,K;
int type[MAXN];
int X[MAXN];
int Y[MAXN];

int main() {
    cin>>N>>K;
    for(int i = 0; i < K; ++i) scanf("%d %d %d", &type[i], &X[i], &Y[i]); // POJ cin 遅い問題対応
    for(int i = 0; i < K; ++i) {--X[i]; --Y[i];}

    init(N*3); // 初期化

    int res = 0;
    for(int i = 0; i < K; ++i) {
        int x = X[i], y = Y[i];
        if(x < 0 || y < 0 || N <= x || N <= y) {
            ++res;
            continue;
        }
        if(type[i] == 1) {
            if(same(x, y + N) || same(x, y + 2*N)) ++res;
            else for(int i = 0; i < 3; ++i) unite(x + i*N, y + i*N); // i が A/B/C に属すこと <=同値=> j が A/B/C に属すこと
        }
        else {
            if(same(x, y) || same(x, y + 2*N)) ++res;
            else {
                unite(x, y + N); // i が A/B/C に属すこと <=同値=> j が B/C/A に属すこと
                unite(x + N, y + 2*N);
                unite(x + 2*N, y);
            }
        }
    }
    cout << res << endl;
    return 0;
}