はまやんはまやんはまやん

hamayanhamayan's blog

部活動調査 [パソコン甲子園2015 予選 G]

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0321?year=2015

前提知識

考察過程

1. 矛盾が発生するのは、ある生徒が2つ以上の部活動に属している可能性がある場合
2. a,bが同じ部活動に属しているということは、同じグループであるとも言える
3. ここでUnionFindな感じが出てくる
4. グループに部活動が割り当てられているので、UnionFindでまとめながら部活動情報も含める感じ
5. この場合に既に部活動が割り当てられているのに別の部活動を割り当てようとするなら矛盾
6. それかUnionFindでマージをするときに異なる部活動なら矛盾
7. これは実装できそう

解説

https://onlinejudge.u-aizu.ac.jp/status/users/hamayanhamayan/submissions/1/0321/judge/3140806/C++14

連結グループにデータをもたせながら、UnionFindする。
連結する際に連結前に入っていたデータをまとめて、連結後の場所に入れる操作をする。
club[i] := i番目のグループの部活動は何か(未割り当てなら-1)
 
連結クエリ
uf[a]とuf[b]が同じでない場合は、club[uf[a]]とclub[uf[b]]のデータを見て、うまくまとめる。
もし一緒なら別にそのままでよい。
違う場合は、片方が-1ならもう片方を採用する。
どちらも違う部活動であれば、違う部活動を1つのグループにしようとしているので、矛盾とする。
aとbを連結した場合は、連結後、uf[a]とuf[b]のどちらかの値になる。
これをnxとしたときのclub[nx]にまとめた結果を入れればいい。
 
部活動クエリ
club[uf[a]]にbを入れればいいが、-1ならそのまま入れる。
そうじゃないなら、矛盾を確認する。

int N, M, K;
int club[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M >> K;
    rep(i, 0, N) club[i] = -1;

    UnionFind uf(N);
    rep(i, 0, K) {
        int t, a, b; cin >> t >> a >> b; a--; b--;
        if (t == 1) {
            if (uf[a] != uf[b]) {
                int aa = uf[a];
                int bb = uf[b];
                uf(a, b);
                int nx = uf[a];
                if (club[aa] != club[bb]) {
                    if (club[aa] < 0) club[nx] = club[bb];
                    else if (club[bb] < 0) club[nx] = club[aa];
                    else {
                        printf("%d\n", i + 1);
                        return;
                    }
                }
            }
        } else {
            if (club[uf[a]] < 0) club[uf[a]] = b;
            else {
                if (club[uf[a]] != b) {
                    printf("%d\n", i + 1);
                    return;
                }
            }
        }
    }
    printf("0\n");
}