【AtCoder】ABC 447 E - Divide Graph

2026-03-01

AtCoder/ABC/E問題 AtCoder/ABC/475点問題 AtCoder/緑Diff AtCoder/NoviSteps/1Q AtCoder/グラフ問題/連結成分に注目する AtCoder/データ構造/Union-Find AtCoder/操作を逆から考える競技プログラミング

E - Divide Graph

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

AtCoder

実行時間制限: 2 sec / メモリ制限: 1024 MiB / Difficulty: 955 / NoviSteps: 1Q / 配点: 475 点

問題概要

$N$ 頂点 $M$ 辺からなる単純連結無向グラフ $G$ が与えられる。頂点には $1$ から $N$ までの、辺には $1$ から $M$ までの番号がそれぞれ付けられており、辺 $i$ は頂点 $U_i$ と頂点 $V_i$ を結んでいる。また、各辺にはコストとよばれる値が定められており、辺 $i$ のコストは $2^i$ である。

今から、 $G$ の連結成分の個数がちょうど $2$ になるように、 $G$ の辺のうちいくつかを選んで削除する。削除する辺のコストの和としてありうる最小値を $998244353$ で割った余りを求めよ。

制約

$2\leq N \leq 2\times 10^5$
$N-1\leq M \leq \min\left(\frac{N(N-1)}{2}, 2\times 10^5\right)$
$1\leq U_i < V_i \leq N$
$i\neq j$ ならば $(U_i, V_i) \neq (U_j, V_j)$
入力は全て整数

考察

まず、辺のコストが $2$ のべき乗になっていることに注目したい。ここで、以下のような式が成り立つ。

\sum_{j=1}^{i-1} 2^j = 2^i - 2 < 2^i

これは、辺 $i$ を削除するコストが、それよりもコストの小さい辺を全て削除するコストの和よりも大きいことを意味している。

したがって、本問の目的を達成するためには、コストが大きい辺の両端点を同じ連結成分にしていくという貪欲的な戦略が成立する。具体的には、以下のようなアルゴリズムとなる。

$N$ 個の頂点をそれぞれ独立な連結成分と見なす。
辺のコストの大きい順に見ていき、その辺が接続する2つの頂点が異なる連結成分に属しているなら、両者を merge する。ただし、連結成分の個数が $2$ 個になったときは打ち切る。
辺のコスト小さい順に見ていき、両端点が異なる連結成分に属している辺のコストを足し合わせる。

データ構造には、Union-Find を用いるとよいだろう。また、ACLのmintを用いて、コストの和を $998244353$ で割った余りを管理すると実装が楽になる。

実装例

1.#include <bits/stdc++.h>
2.using namespace std;
3. 
4.#if __has_include(<atcoder/all>)
5.#include <atcoder/all>
6.using namespace atcoder;
7.#endif
8. 
9.#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)
10.#define rrep(i, start, end) for (auto i = (start); (i) >= (end); (i)--)
11. 
12.using mint = modint998244353;
13.using Pair_int = pair<int, int>;
14. 
15.// ======================================== //
16. 
17.int main()
18.{
19.    int N, M;
20.    cin >> N >> M;
21.    vector<Pair_int> edges(M);
22.    rep(i, 0, M)
23.    {
24.        int U, V;
25.        cin >> U >> V;
26.        U--, V--;
27.        edges[i] = {U, V};
28.    }
29. 
30.    dsu uf(N);
31.    int cnt = N;
32.    rrep(i, M - 1, 0)
33.    {
34.        if (cnt <= 2)
35.            break;
36. 
37.        if (!uf.same(edges[i].first, edges[i].second))
38.        {
39.            uf.merge(edges[i].first, edges[i].second);
40.            cnt--;
41.        }
42.    }
43. 
44.    mint ans = 0;
45.    mint pow2 = 2;
46.    rep(i, 0, M)
47.    {
48.        if (!uf.same(edges[i].first, edges[i].second))
49.        {
50.            ans += pow2;
51.        }
52.        pow2 *= 2;
53.    }
54. 
55.    cout << ans.val() << endl;
56. 
57.    return 0;
58.}