PAT 甲级测试题目 -- 1013 Battle Over Cities

题目描述

给你城市的数量 N(N<1000)，城市中地铁的数量 M 以及被可能占领的城市数量 K（每一次只占领一个城市，并且每次占领的城市不一样），接下来的 M 行根据地铁的数量给出每个地铁连接的两个城市编号。最后一行给你被占领的城市序列。城市编号为 1 到 N，请你求出若某个城市被占领了，连通剩下城市所需要修建的地铁个数。

分析

该题考察图的存储以及遍历。本题的难点在于把 “需要维修多少个地铁” 这个问题转换成 “需要多少次 dfs 才能遍历完整个图”。因为倘若图不是连通的，则它的各个部分需要执行大于 1 次的 DFS 才能够遍历图中的每一个节点。

实现

#include <iostream>
#include <string.h>

using namespace std;

#define maxn 1001

// 变量定义
int total_cities, highways, check_cities; // 总城市 城市之间的地铁 被检查的城市
bool highway_map[maxn][maxn]; // 定义地铁地图
int check_list[maxn];   // 定义检查列表用于存储检查的城市
bool checked_cities[maxn]; // 判断是否检查过这个城市

// 定义方法递归实现 dfs 遍历节点
void CheckHighway(int source_city) {
    // 没查看过就标记为已查看
    checked_cities[source_city] = true;
    // 查看当前城市连接的城市
    for (int i = 1; i <= total_cities; ++i) {
        // 若该城市没被检查过（缩短递归次数）并且 含有该城市
        if (!checked_cities[i] && highway_map[source_city][i])
            CheckHighway(i);
    }

}

int main() {
    // 初始化变量
    scanf("%d%d%d", &total_cities, &highways, &check_cities);

    for (int i = 0; i < highways; ++i) {             // 构建城市地铁图
        int source_city, aim_city;  // 定义变量接收 源城市 目标城市
        scanf("%d%d", &source_city, &aim_city);
        highway_map[source_city][aim_city] = true; // 将两个城市对应的值均设置为 true，表示两城市是连通的
        highway_map[aim_city][source_city] = true;
    }

    for (int i = 0; i < check_cities; ++i) {    // 构建检查城市列表
        scanf("%d", &check_list[i]);
    }

    // 计算需要维修公路的数量
    int times = 0; // 计算需要维修多少条公路
    for (int i = 0; i < check_cities; ++i) {    // 根据需要检查的城市数量检查城市
        times = 0;
        memset(checked_cities, false, sizeof(checked_cities)); // 初始化已检查过的城市为 false
        checked_cities[check_list[i]] = true; // 将被掠夺的城市设置为 true
        for (int j = 1; j <= total_cities; ++j) {
            if(!checked_cities[j]){
                times++;
                CheckHighway(j);
            }
        }
        printf("%d
", times-1);
        
    }
}

自己碰上的难点

初期实现的时候打算使用 map<int, vector> 数据类型存储图，最后时间空间均超限。
然后使用 bool 类型的二维数组存储图，并且数据类型能用 bool 尽量用 bool，最大的数据类型只是 int。解决了空间存储问题，但是仍未解决时间问题
去网上看了一个 AC 代码，尝试将 cout 和 cin 换成 printf 以及 scanf。代码 AC 了
结论：对于可以不用 STL 的并且需要存储大量数据，执行多次循环的代码，使用 c 风格代码较好