【AtCoder】ABC 401 E - Reachable Set | 緑コーダーが解くAtCoder

atcoder.jp

配点: 450 点 / 実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: ???

問題概要
制約
考察
実装例
コメント

問題概要

$N$ 頂点 $M$ 辺の無向グラフがある。頂点には $1,2,\cdots,N$ の番号がついており、 $i$ 番目の辺は頂点 $u_i$ と頂点 $v_i$ を結んでいる。

$k=1,2,\cdots,N$ について、次の問題を解け。

「頂点を一つ選び、選んだ頂点とそれに接続する全ての辺をグラフから削除する」という操作を繰り返すことで、次の条件を満たすことができるか判定し、不可能なら-1を出力、可能なら条件を満たすために少なくとも何回操作を行う必要があるか求めよ。

頂点 $1$ から辺をたどって到達できる頂点の集合が、頂点 $1, 2,\cdots, k$ のちょうど $k$ 個からなる。

制約

$1\leq N\leq2\times10^5$
$0\leq M\leq3\times10^5$
$1\leq u_i\lt v_i\leq N$
入力はすべて整数

考察

この問題は「可能性の判定」と「操作回数の最小化」の2つのパートに分けて考えることができる。

可能性の判定

「頂点 $1$ から辺をたどって到達できる頂点の集合が、頂点 $1, 2,\cdots, k$ のちょうど $k$ 個からなる」状態というのは、

ある $k$ に対して、頂点 $1$ から任意の頂点 $v \: (1 \lt v \leq k)$ へ、 番号が $k$ より大きな頂点を経由せずに到達できる

ということである。

番号が $k$ より大きな頂点を経由したくないのだから、このような頂点を全て削除した上で、

頂点 $1$ が含まれる連結成分の大きさが $k$ (残りの連結成分がただ1つ)

であるならば、この $k$ については問題文の条件を満たすことができると言える。

これを後の実装のために言い換えておくと、

「辺で連結されている2頂点のうち、番号の大きい方が $k$ 以下であるような辺のみで構成される部分グラフ」上で、頂点 $1$ を含む連結成分の大きさが $k$ である

ということが判定条件になる。

操作回数の最小化

さて、前項では番号が $k$ より大きな頂点を全て削除したが、実は頂点を消し過ぎていることに気づくだろうか？

サンプルケース1を例にとって考えてみる。

$k = 2$ のときについて、番号が $2$ より大きい頂点をすべて削除した。

これでも問題文の条件は満たしているのだが、よく考えると頂点 $6$ は残しておいてもいいような気がする。

頂点 $1, 2$ は頂点 $6$ と元のグラフ上で隣接していないため、上図のように残しても頂点 $1$ から頂点 $6$ へは到達できず、結果的に条件は満たしていることになる。

つまり、削除すべきなのは「番号が $k$ 以下の頂点に隣接している頂点のみ」であることが分かった。

この個数は、「番号が $k$ 以下の頂点を端点の1つとして持つ辺のみで構成される部分グラフ」上で、頂点 $1$ を含む連結成分の大きさから、 $k$ を引いたものに等しい。画像も参考に...

実装にあたって

さて、あとは上述の考察をもとに実装していくわけだが、まずデータ構造としては Union-Find が適当である。これは、各パートで連結成分の大きさを求める必要があるためだ。

今回は、 ACL の DSU を用いることにする。

また、2つのパートでは考えるべき部分グラフが異なっているので、 Union-Find も2つ用意することで、部分グラフを構築しながら可能性の判定と操作の最小化を同時に行うことができるようになる。実装例では前者をuf_1、後者をuf_2とした。

なお、実装例では 0-indexed になっていることに注意してほしい。

実装例

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

#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#endif

#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)

template <class T>
using Graph = vector<vector<T>>;

// ======================================== //

int main()
{
    int N, M;
    cin >> N >> M;
    Graph<int> G(N);
    rep(i, 0, M)
    {
        int u, v;
        cin >> u >> v;
        u--, v--;
        G[u].push_back(v);
        G[v].push_back(u);
    }

    dsu uf_1(N), uf_2(N);
    rep(k, 0, N)
    {
        for (auto &&v : G[k])
        {
            if (v < k)
                uf_1.merge(k, v);
            else
                uf_2.merge(k, v);
        }

        if (uf_1.size(0) == k + 1)
            cout << uf_2.size(0) - (k + 1) << endl;
        else
            cout << -1 << endl;
    }

    return 0;
}