AOJ 0321 Investigation of Club Activities

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0321

解法

union find 木を使うと楽？
union find の各集合がどのクラブに属するかを別に vector で持っておく．
a と b が同じ部活に所属している場合，マージするのだが違うクラブに属している（少なくともどちらか一方の集合のクラブの情報がない場合はセーフ）ならアウト．
c が部活 x に属しているとき，c の属する集合のクラブの情報と比べて違えばダメ．まだクラブの情報がないなら x を書き込む．
これを上から順番にやる．

ソースコード

#include <bits/stdc++.h>
using namespace std;

class union_find {
public:
    union_find(int n) : par(n, -1) {}
    int root(int x) { return par[x] < 0 ? x : par[x] = root(par[x]); }
    bool same(int x, int y) {
        return root(x) == root(y);
    }
    void unite(int x, int y) {
        x = root(x), y = root(y);
        if(x == y) return;
        if(par[x] > par[y]) swap(x, y);
        par[x] += par[y];
        par[y] = x;
    }
private:
    vector<int> par;
};

int main() {
    int n, m, k;
    cin >> n >> m >> k;
    union_find uf(n);
    vector<int> club(n, -1);
    int ans = 0;
    for(int i = 0; i < k; ++i) {
        int type; cin >> type;
        if(type == 1) {
            int a, b;
            cin >> a >> b;
            a--; b--;
            int ra = uf.root(a), rb = uf.root(b);
            if(club[ra] == -1 || club[rb] == -1 || club[ra] == club[rb]) {
                uf.unite(a, b);
                club[uf.root(a)] = max(club[ra], club[rb]);
            } else {
                ans = i + 1;
                break;
            }
        } else {
            int c, x;
            cin >> c >> x;
            c--; x--;
            if(club[uf.root(c)] == -1 || club[uf.root(c)] == x) {
                club[uf.root(c)] = x;
            } else {
                ans = i + 1;
                break;
            }
        }
    }
    cout << ans << endl;
}

感想

PCK予選って解説無いんですかね？