【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就是几个连通分量。

首先维护一个访问集合inMap，保存访问到的城市，
当失去一个城市后，以每个未被访问过的城市为起点进行dfs，将dfs到的城市归入集合inMap。（所以之后再遍历到该城市就不会再dfs了）
当我们开始一系列的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;
}