Chokudai SpeedRun 002 K - 種類数 β (600 点)

これがこのセットで一番難しかった。
こういうのをグラフで考えるのは典型と言えば典型か。

問題へのリンク

問題概要

組の整数組 がある。それぞれの組から整数を選んだ 種類の整数に含まれる整数の種類数の最大値を求めよ。

制約

• 

考えたこと

数値をノードにもち、 となる が存在するときにノード u と v とを結ぶようなグラフを考えてみる。この手のグラフで考えてみようと試みるまでは典型っぽい。このグラフにおいては、自己ループがありうることに注意。

で、とりあえず連結成分ごとに考えればよくて、各連結成分ごとに

• (頂点数, 辺数) のうちの小さい方

しかとれないことは明らかで、それがとれることも示せる。

#include <iostream>
#include <vector>
#include <set>
using namespace std;
using pint = pair<int,int>;

struct UnionFind {
    vector<int> par, w;
    
    UnionFind(int n) : par(n, -1), w(n, 0) { }
    void init(int n) { par.assign(n, -1); w.assign(n, 0); }
    
    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) {
            ++w[x];
            return false;
        }
        if (par[x] > par[y]) swap(x, y); // merge technique
        par[x] += par[y];
        par[y] = x;
        w[x] += w[y];
        ++w[x];
        return true;
    }
    
    int size(int x) {
        return -par[root(x)];
    }
 
    int wei(int x) {
        return w[root(x)];
    }
};

 
int main() {
    int N; cin >> N;
    vector<long long> alt; // 座標圧縮
    vector<long long> A(N), B(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i] >> B[i];
        if (A[i] > B[i]) swap(A[i], B[i]);
        alt.push_back(A[i]);
        alt.push_back(B[i]);
        }
    sort(alt.begin(), alt.end());
    alt.erase(unique(alt.begin(), alt.end()), alt.end());
    int M = alt.size();
    
    UnionFind uf(M);
    for (int i = 0; i < N; ++i) {
        int a = lower_bound(alt.begin(), alt.end(), A[i]) - alt.begin();
        int b = lower_bound(alt.begin(), alt.end(), B[i]) - alt.begin();
        uf.merge(a, b);
    }
    
    int res = 0;
    set<int> se;
    for (int i = 0; i < M; ++i) {
        int r = uf.root(i);
        if (se.count(r)) continue;
        se.insert(r);
        res += min(uf.wei(r), uf.size(r));;
    }
    cout << res << endl;
}