【PAT甲级题解记录】1013 Battle Over Cities (25 分)

【PAT甲级题解记录】1013 Battle Over Cities (25 分)

前言

Problem：1013 Battle Over Cities (25 分)

Tags：DFS 连通图

Difficulty：剧情模式 想流点汗 想流点血 死而无憾

Address：1013 Battle Over Cities (25 分)

问题描述

给出一个城市和公路的连通图（虽然题目里没有明确说明），城市编号1-N。

每一次询问都独立输入一个城市编号，求删去这个城市后需要至少加几条路使得连通图成立。

解题思路

其实就是求连通分量数量，想了想试了试没有想到很巧妙的方法，那还是用搜索稳一点：以每个城市为起点开一个dfs，如果被搜索过就直接跳过，最后开了几个dfs就是几个连通分量。

1. 首先维护一个访问集合inMap，保存访问到的城市，
2. 当失去一个城市后，以每个未被访问过的城市为起点进行dfs，将dfs到的城市归入集合inMap。（所以之后再遍历到该城市就不会再dfs了）
3. 当我们开始一系列的dfs时对ans累加1（说明这是一个被隔开的城市），ans最终的值说明了有多少个连通分量，ans-1就是要修的公路数量（N个连通分量只需要N-1条路径来实现整张图的连通）

参考代码

#include<iostream>
#include<vector>
#include<set>using namespace std;
int N, M, K;
vector<vector<int>> edges; 
set<int> inMap; // 用于确认某个城市是否已被搜索
int occupied_city;void init() {cin >> N >> M >> K;edges.resize(N + 1);for (int i = 0; i < M; i++) {int city1, city2;cin >> city1 >> city2;edges[city1].push_back(city2);edges[city2].push_back(city1);}
}void dfs(int root) {inMap.insert(root);int num = edges[root].size();for (int i = 0; i < num; i++) {int next_city = edges[root][i];if (inMap.count(next_city) == 0) {dfs(edges[root][i]);}}
}void solve() {inMap.clear(); // 每次查询都需清空集合int ans = 0; // 连通分量数量cin >> occupied_city;inMap.insert(occupied_city);for (int i = 1; i <= N; i++) {if (inMap.count(i) || i == occupied_city) continue;dfs(i);ans++;}cout << ans - 1 << endl;}void solution_1013() {init();for (int i = 0; i < K; i++) {solve();}
}
int main() {solution_1013();return 0;
}

总结

关于图的连通等问题，用DFS解决很常见。