【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解决很常见。