Peter_Matthew的博客

题解 GPLT L2-025 分而治之

2025-08-06

本文共328字,大约需要阅读1分钟。

图论问题,邻接表建图;
对每组方案用 unordered_set 存储要移除的城市,用另一个 unordered_set 存储剩下的城市,遍历剩余城市的邻接边,只要找到一个邻居也在剩余城市中,说明它们之间仍然连通,若无此情况,输出 YES,否则输出 NO。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<bits/stdc++.h>
using namespace std;

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);

int N, M;
cin >> N >> M;

vector<vector<int> > graph(N + 1); // 城市编号从1开始

// 构建无向图的邻接表
for (int i = 0; i < M; ++i) {
int u, v;
cin >> u >> v;
graph[u].push_back(v);
graph[v].push_back(u);
}

int K;
cin >> K;

for (int i = 0; i < K; ++i) {
int Np;
cin >> Np;
unordered_set<int> to_remove;
for (int j = 0; j < Np; ++j) {
int city;
cin >> city;
to_remove.insert(city);
}

// 构建剩余城市集合
unordered_set<int> remaining;
for (int city = 1; city <= N; ++city) {
if (to_remove.find(city) == to_remove.end()) {
remaining.insert(city);
}
}

// 检查剩余城市是否之间有连接
bool isolated = true;
for (int u : remaining) {
for (int v : graph[u]) {
if (remaining.find(v) != remaining.end()) {
// u 和 v 都在剩余城市集合中,说明还有边
isolated = false;
break;
}
}
if (!isolated) break;
}

cout << (isolated ? "YES" : "NO") << '\n';
}

return 0;
}
标签: 题解
使用支付宝打赏
使用微信打赏

若你觉得我的文章对你有帮助,欢迎点击上方按钮对我打赏