下手を打つと密なグラフになって TLE してしまう！！
スーパーノードを作ることでグラフを sparse にするテク！

問題へのリンク

問題概要

$1$ 以上 $M$ 以下の整数値からなる $N$ 個の有限集合 $S_{1}, S_{2}, \dots, S_{N}$ が与えられる。

以下の操作を最小回数繰り返すことによって、「 $1$ と $M$ をともに含む有限集合が存在する状態」を作り出したい。

有限集合を 2 つ選ぶ ( $X, Y$ とする)
$X, Y$ を削除する
$X \cup Y$ を追加する

1 回の操作によって、集合の個数は 1 減ることとなる。目的を達するための操作回数の最小値を求めよ。不可能な場合は -1 を出力せよ。

制約

$1 \le N \le 2 \times 10^{5}$
$2 \le M \le 2 \times 10^{5}$
$1 \le \sum_{i=1}^{N} |S_{i}| \le 5 \times 10^{5}$

考えたこと

パッと思い浮かぶのは、各集合に対応する $N$ 頂点を用意して、 $S_{i} \cap S_{j} \neq \emptyset$ なる $i, j$ 間に辺を張ったグラフ上で BFS する方法だ。しかしこれでは、辺数 $O(N^{2})$ のグラフとなってしまう。このグラフで BFS したのでは、TLE となってしまう。

そこで、スーパーノードを用意することで、グラフを sparse にするテクを使う！！

$N$ 個の頂点に加えて、値 $1, 2, \dots, M$ に対応する $M$ 個の頂点を加える。合計 $N + M$ 個の頂点からなるグラフを作る。

そして、 $j \in A_{i}$ であるとき、2 頂点 $i, j+N$ の間に辺を張るようにする。こうしてできるグラフにおいて、「値 1 に対応する頂点」と「値 $M$ に対応する頂点」との距離を $d$ として、 $\frac{d}{2} - 1$ を答えればよい。

このグラフは、 $E = \sum_{i=1}^{N} |S_{i}|$ として、

頂点数： $N + M$
辺数： $E$

なので、BFS したときの計算量は $O(N + M + E)$ となる。十分間に合う。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, M;
    cin >> N >> M;
    
    // グラフを作る
    vector<vector<int>> G(N + M);
    for (int i = 0; i < N; ++i) {
        int A;
        cin >> A;
        for (int j = 0; j < A; ++j) {
            int S;
            cin >> S;
            --S;
            G[i].push_back(S+N);
            G[S+N].push_back(i);
        }
    }
    
    // 頂点 N, M-1+N の間の足短距離を求める
    int s = N, t = M-1+N;
    queue<int> que;
    vector<int> dist(N + M, -1);
    que.push(s);
    dist[s] = 0;
    while (!que.empty()) {
        int v = que.front();
        que.pop();
        for (auto v2 : G[v]) {
            if (dist[v2] == -1) {
                que.push(v2);
                dist[v2] = dist[v] + 1;
            }
        }
    }
    cout << dist[t]/2 - 1 << endl;
}

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

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

AtCoder ABC 302 F - Merge Set (水色, 500 点)

問題概要

制約

考えたこと

コード