Codeforces 500 DIV1 B. Chemical table (R1900)

確かに、ついこの間の ABC 131 F の類題だね

問題へのリンク

問題概要

のグリッドがあって、 マス分が黒く塗られている

• 長方形の三頂点状に並んだ黒マスの組を選んで、残りの頂点に相当する位置を黒く塗る (コスト 0)
• 黒くないマスを一つ選んで黒く塗る (コスト 1)

という操作を繰り返して全マスを黒くしたい。これを達成するための最小コストを求めよ。

考えたこと

これとほぼ一緒。
これと同じように二部グラフを作り、「連結成分の個数 - 1」を答えればよい。

drken1215.hatenablog.com

#include <iostream>
#include <vector>
#include <set>
using namespace std;

struct UnionFind {
    vector<int> par;
    
    UnionFind(int n) : par(n, -1) { }
    void init(int n) { par.assign(n, -1); }
    
    int root(int x) {
        if (par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }
    
    bool issame(int x, int y) {
        return root(x) == root(y);
    }
    
    bool merge(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (par[x] > par[y]) swap(x, y); // merge technique
        par[x] += par[y];
        par[y] = x;
        return true;
    }
    
    int size(int x) {
        return -par[root(x)];
    }
};

int main() {
    int N, M, Q;
    cin >> N >> M >> Q;
    UnionFind uf(N+M);
    for (int q = 0; q < Q; ++q) {
        int x, y; cin >> x >> y; --x, --y;
        uf.merge(x, y+N);
    }
    set<int> se;
    for (int r = 0; r < N+M; ++r) se.insert(uf.root(r));
    cout << (int)se.size() - 1 << endl;
}