AtCoder Beginner Contest 447 E

RookieSama_

公告

欢迎来到小破站ようこそ私のブログへ！

Learn Morea

标签

413 字

2 分钟

AtCoder Beginner Contest 447 E

2026-03-01

题解

ABC

/

并查集

/

贪心

E - Divide Graph #

题目大意：#

现在给你 n 个点， m 条边，现在让你删除一些边使得，这个图正有 2 条连通分量
- 连通分量：如果从一个顶点，都存在路径到达另一个顶点，则顶点称为连通的。
现在让你求出，最小代价使得有 2 条连通分量。

解题思路#

由于删除第 i 条边的代价是： $2^i > 2^{i-1} + ... + 2^1$ ，所以，越是后面的边越是要保留，因此建图要从后面的边开始建
只有当两个点连接后连通分量 $cnt - 1 < 2$ 时不能够连边
判断两个点连接后，连通分量 cnt 是否会减少主要依据是否在同一个集合中，这里我们用 [[并查集]] 去判断。

易错点：#

注意要 mod 并且计算 $2^i$ 要用快速幂(qpow)

代码：#

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

4
using PII = pair<int, int>;
5
#define int long long
6
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
7
const int N = 5e5 + 10, mod = 998244353;
8

9
int n, m;
10
class Node{
11
public:
12
    int u, v;
13
};
14
Node a[N];
15
int p[N];
16

17
int find(int x){
18
    if(p[x] != x) p[x] = find(p[x]);
19
    return p[x];
20
}
21

22
int qpow(int x, int k){
23
    int res = 1;
24
    while(k){
25
        if(k & 1) res = res * x % mod;
26
        x = x * x % mod;
27
        k >>= 1;
28
    }
29
    return res;
30
}
31

32
void solve(){
33
    cin >> n >> m;
34
    for(int i = 1; i <= n; i++) p[i] = i;
35
    for(int i = 1; i <= m; i++){
36
        cin >> a[i].u >> a[i].v;
37
    }
38

39
    int cnt = n, ans = 0;
40

41
    for(int i = m; i >= 1; i--){
42
        int u = a[i].u, v = a[i].v;
43
        if(find(u) != find(v)){
44
            if(cnt - 1 >= 2){
45
                p[find(u)] = find(v);
46
                cnt--;
47
            }else{
48
                ans = (ans + qpow(2, i)) % mod;
49
            }
50
        }
51
    }
52
    cout << ans << endl;
53
}
54

55
signed main(){
56
    IOS;
57
    int _ = 1;
58
    //cin >> _;
59
    while(_--){
60
        solve();
61
    }
62
}