けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

Codeforces Round #584 - Dasha Code Championship D. Cow and Snacks (R1700)

面白かった!

問題へのリンク

問題概要

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

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

制約

  •  n, k \le 10^{5}

考えたこと

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

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

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

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

#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;
}