Codeforces Round #584 (Div. 1 + Div. 2) D. Cow and Snacks (R1700)

面白かった！

問題へのリンク

問題概要

組の 2 整数 () があたえられる。 を満たす。この 組の 通りの順序すべてを考えたときの以下のように定義される「悲しみ」の最小値を求めよ。　

• 「これまでに登場した整数」を表す集合を とする
• 各 i について、 がともに に属するとき、「悲しみ」が 1 増える。また を に追加する

制約

• 

考えたこと

順序を最適化する問題！！！！！
そういうのは大好き！！！！！　　

さて、各組 () を Union-Find で と を併合するものと考えたとき、

• 各グループについて独立に考えて良い
• 各グループについて、グループに含まれる整数が 個であるとき、その中で悲しみを感じない整数の個数はどう頑張っても 個までである (その 個は達成できる)

ということがわかる。よって、悲しみを感じずにすむ組の個数は、 - (グループの個数) となる。

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

struct UnionFind {
    vector<int> par;
    int count;
    
    UnionFind(int n) : par(n, -1), count(n) { }
    void init(int n) { par.assign(n, -1); count = n; }
    
    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;
        --count;
        return true;
    }
    
    int size(int x) {
        return -par[root(x)];
    }
};

int main() {
    int N, K; cin >> N >> K;
    UnionFind uf(N);
    for (int i = 0; i < K; ++i) {
        int x, y; cin >> x >> y; --x, --y;
        uf.merge(x, y);
    }
    cout << K - (N - uf.count) << endl;
}