难题解答 - 第10-11周理论作业（第5次）

文章摘要

LCY AI Pro

本文汇总第10-11周（第5次）理论作业的题目、参考代码与要点解析，聚焦 BFS/DFS 在邻接矩阵、邻接表与网格上的应用。

1.图的遍历及连通性

---

原题再现

【问题描述】
根据输入的图的邻接矩阵 $A$，判断此图的连通分量的个数。请使用 邻接矩阵 的存储结构创建图的存储，并采用 BFS 优先遍历算法实现，否则不得分。
【输入形式】
第一行为图的结点个数 $n$，之后的 $n$ 行为邻接矩阵的内容，每行 $n$ 个数表示。其中 A[i][j]=1 表示两个结点邻接，而 A[i][j]=0 表示两个结点无邻接关系。
【输出形式】
输出此图连通分量的个数。
【样例输入】
5
0 1 1 0 0
1 0 1 0 0
1 1 0 0 0
0 0 0 0 1
0 0 0 1 0
【样例输出】
2
【样例说明】
邻接矩阵中对角线上的元素都用 0 表示。(单个独立结点，即与其它结点都没有边连接，也算一个连通分量)

参考代码

#include <bits/stdc++.h>
using namespace std;

void bfs(int start, int n, const vector<vector<int>>& matrix, vector<bool>& visited) {
    queue<int> q;
    q.push(start);
    visited[start] = true;
    while (!q.empty()) {
        int current = q.front();
        q.pop();
        for (int i = 0; i < n; i++) {
            if (matrix[current][i] == 1 && !visited[i]) {
                q.push(i);
                visited[i] = true;
            }
        }
    }
}

int main() {
    int n;
    cin >> n;
    vector<vector<int>> matrix(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> matrix[i][j];
        }
    }
    vector<bool> visited(n, false);
    int connected_components = 0;
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            connected_components++;
            bfs(i, n, matrix, visited);
        }
    }
    cout << connected_components << endl;
    return 0;
}

逐块精析

1. 广度优先搜索（BFS）

    void bfs(int start, int n, const vector<vector<int>>& matrix, vector<bool>& visited) {
    queue<int> q; // 定义辅助队列，用于暂存待扩展的结点
    q.push(start); // 将遍历的起点入队
    visited[start] = true; // 立即将起点标记为已访问，防止重复入队
    while (!q.empty()) {
        int current = q.front(); // 获取队首结点
        q.pop(); // 弹出队首结点
        // 遍历邻接矩阵的当前行，查找所有与 current 邻接的结点
        for (int i = 0; i < n; i++) {
            // 如果 current 与 i 存在边（值为1），且结点 i 未被访问
            if (matrix[current][i] == 1 && !visited[i]) {
                q.push(i); // 将邻居结点 i 入队
                visited[i] = true; // 标记结点 i 为已访问
            }
        }
    }
}

解析：该功能块实现了标准的广度优先搜索。利用队列先进先出的特性，逐层向外扩展。在邻接矩阵中，判断两个结点是否连通需要遍历一整行（即 matrix[current][i] == 1），时间复杂度为 $O(n)$。

2. 数据读入与存储初始化

int n;
cin >> n;
// 定义二维动态数组，构建 n * n 的邻接矩阵
vector<vector<int>> matrix(n, vector<int>(n));
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        cin >> matrix[i][j]; // 循环读入矩阵的每一个元素
    }
}

解析：此块负责解析输入数据。利用 C++ 的 std::vector 动态开辟二维空间。通过嵌套循环将标准输入的矩阵流存入内存，为后续的图遍历做准备。

3. 遍历主控逻辑与计数

vector<bool> visited(n, false); // 初始化访问标记数组，初始值均为未访问
int connected_components = 0; // 计数器，记录连通分量的个数
// 依次检查每一个结点
for (int i = 0; i < n; i++) {
    // 如果发现某个结点尚未被访问，说明它属于一个新的连通分量
    if (!visited[i]) {
        connected_components++; // 连通分量计数加 1
        bfs(i, n, matrix, visited); // 激活 BFS，将该连通分量内的所有结点全部标记
    }
}
cout << connected_components << endl; // 输出最终结果

解析：该部分是统计连通分量的核心。外层循环遍历所有结点，一旦遇到 visited[i] == false 的情况，说明捕获到了一个新的连通分量。此时计数器自增，并调用 bfs() 函数。该搜索会把当前连通分量内的所有结点“染色”为 true，确保后续循环不会重复计数。

---

2.犯罪团伙

原题再现

【题目描述】
此题必须采用 邻接表 的存储结构，建立图的存储，然后采用 DFS 遍历实现求解。否则不给分。
警察抓到了 $n$ 个罪犯，警察根据经验知道他们属于不同的犯罪团伙，却不能判断有多少个团伙，但通过警察的审讯，知道其中的一些罪犯之间相互认识，已知同一犯罪团伙的成员之间直接或间接认识。有可能一个犯罪团伙只有一个人。请根据已知罪犯之间的关系，确定犯罪团伙的数量。已知罪犯的编号从 $1$ 至 $n$ 。
【输入】
第一行：$n$（$<=1000$,罪犯数量），第二行：$m$（$<5000$，关系数量）以下若干行：每行两个数：$i$和$j$，中间一个空格隔开，表示罪犯$i$和罪犯$j$相互认识。
【输出】
一个整数，犯罪团伙的数量。
【样例输入】
11
8
1 2
4 3
5 4
1 3
5 6
7 10
5 10
8 9
【样例输出】
3

参考代码

#include <bits/stdc++.h>
using namespace std;

void dfs(int current, const vector<vector<int>>& adj_list, vector<bool>& visited) {
    visited[current] = true;
    for (int neighbor : adj_list[current]) {
        if (!visited[neighbor]) {
            dfs(neighbor, adj_list, visited);
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> adj_list(n + 1);
    for (int k = 0; k < m; k++) {
        int i, j;
        cin >> i >> j;
        adj_list[i].push_back(j);
        adj_list[j].push_back(i);
    }
    vector<bool> visited(n + 1, false);
    int gang_count = 0;
    for (int i = 1; i <= n; i++) {
        if (!visited[i]) {
            gang_count++;
            dfs(i, adj_list, visited);
        }
    }
    cout << gang_count << endl;
    return 0;
}

逐块精析

1. 深度优先搜索（DFS）

    void dfs(int current, const vector<vector<int>>& adj_list, vector<bool>& visited) {
    visited[current] = true; // 将当前结点标记为已访问
    // 遍历当前结点的邻接链表，直接获取所有相邻结点
    for (int neighbor : adj_list[current]) {
        // 如果邻居结点未被访问，则递归进入该邻居结点进行深度搜索
        if (!visited[neighbor]) {
            dfs(neighbor, adj_list, visited);
        }
    }
}

解析：这里采用了深度优先搜索。通过递归调用，算法会沿着一条路径一直走到底，再回溯探测其他分支。在邻接表结构中，遍历当前结点的邻居非常高效，只需遍历 adj_list[current] 这个单维容器，避免了邻接矩阵不必要的空遍历。

2. 邻接表的动态构建

int n, m;
cin >> n >> m;
// 罪犯编号为 1 到 n，因此开辟大小为 n + 1 的数组以对齐索引
vector<vector<int>> adj_list(n + 1);
for (int k = 0; k < m; k++) {
    int i, j;
    cin >> i >> j;
    adj_list[i].push_back(j); // 添加正向边：i 认识 j
    adj_list[j].push_back(i); // 添加反向边：j 认识 i（无向图特征）
}

解析：由于题目中罪犯的编号是从 1 到 n，为了代码可读性与防越界，邻接表的大小被设定为 n + 1。因为“认识”是双向关系，所以每读入一条边，都需要在两个结点的邻接链表中分别执行 push_back()。

3. 连通分量计数主循环

vector<bool> visited(n + 1, false); // 同样开辟 n + 1 大小的标记数组
int gang_count = 0; // 犯罪团伙（连通分量）计数器
// 从编号 1 到 n 依次遍历
for (int i = 1; i <= n; i++) {
    // 如果该罪犯未被归入任何团伙
    if (!visited[i]) {
        gang_count++; // 发现新团伙，计数加 1
        dfs(i, adj_list, visited); // 通过 DFS 将该团伙的所有成员一网打尽
    }
}
cout << gang_count << endl; // 输出最终的团伙数量

解析：主控制逻辑与第一题类似，区别在于循环边界变为了 1 到 n。dfs() 函数执行完毕后，所有相互认识（直接或间接）的罪犯状态均会被置为 true。

---

3.油田问题

原题再现

【问题描述】
GeoSurvComp地质探测公司负责探测地下油田。每次GeoSurvComp公司都是在一块长方形的土地上来探测油田。在探测时，他们把这块土地用网格分成若干个小块，然后逐个分析每块土地，用探测设备探测地下是否有油田。土地底下有油田则成为pocket，如果两个pocket相邻，则认为是同一块油田，油田可能覆盖多个pocket。试计算长方形的土地上有多少个不同的油田。
【输入形式】
输入文件中包含多个测试数据，每个测试数据描述了一个网格。每个网格数据的第1行为两个整数：$m$、$n$，分别表示网格的行和列；如果$m=0$，则表示输入结束，否则 $1<=m<=100$， $1<=n<=100$。接下来有$m$行数据，每行数据有$n$个字符（不包括行结束符）。每个字符代表一个小方块，如果为“*”，则代表没有石油，如果为“@”，则代表有石油，是一个pocket。
【输出形式】
对输入文件中的每个网格，输出网格中不同的油田数目。如果两块不同的pocket在水平、垂直或者对角线方向上相邻，则被认为属于同一块油田。每块油田所包含的pocket数目不会超过$100$。
【样例输入】
5 5
****@
*@@*@
*@**@
@@@*@
@@**@
【样例输出】
2

参考代码

#include <bits/stdc++.h>
using namespace std;

int dx[] = {-1, 1, 0, 0, -1, -1, 1, 1};
int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};

void dfs(int x, int y, int m, int n, vector<string>& grid) {
    grid[x][y] = '*';
    for (int i = 0; i < 8; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] == '@') {
            dfs(nx, ny, m, n, grid);
        }
    }
}

int main() {
    int m, n;
    while (cin >> m >> n && m != 0) {
        vector<string> grid(m);
        for (int i = 0; i < m; i++) {
            cin >> grid[i];
        }
        int oil_fields = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '@') {
                    oil_fields++;
                    dfs(i, j, m, n, grid);
                }
            }
        }
        cout << oil_fields << endl;
    }
    return 0;
}

逐块精析

1. 方向数组与网格 DFS 实现

// 定义八个方向的横纵坐标偏移量（上下左右 + 四个斜对角）
int dx[] = {-1, 1, 0, 0, -1, -1, 1, 1};
int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};

void dfs(int x, int y, int m, int n, vector<string>& grid) {
    grid[x][y] = '*'; // 原地修改：将当前 '@' 改为 '*'，避免引入额外的 visited 空间
    // 循环遍历当前格子的 8 个邻居
    for (int i = 0; i < 8; i++) {
        int nx = x + dx[i]; // 计算邻居的行坐标
        int ny = y + dy[i]; // 计算邻居的列坐标
        // 确保边界合法，并且该邻居也是尚未处理的油田 pocket
        if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] == '@') {
            dfs(nx, ny, m, n, grid); // 递归扩散
        }
    }
}

解析：在网格图像搜索中，定义 dx 和 dy 数组可以大幅简化代码结构。这里使用的是“原地标记法”，直接将遍历过的 @ 字符修改为 *，既能防止重复访问导致的死循环，又消除了空间开销。

2. 多组数据读入处理

int m, n;
// 循环读取数据，直到遇到 m 为 0 时终止退出
while (cin >> m >> n && m != 0) {
    vector<string> grid(m);
    for (int i = 0; i < m; i++) {
        cin >> grid[i]; // 读入长度为 n 的字符串，作为网格的一行
    }

解析：本块实现了多组测试数据的安全读入。通过 while (cin >> m >> n && m != 0) 结构，能够连续处理多个不同的地图网格，直至接收到停机信号。

3. 全局扫描与结果输出

    int oil_fields = 0; // 记录当前网格的油田（连通分量）数量
    // 嵌套循环遍历二维网格的每一个格子
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            // 如果发现一块属于新油田的 pocket
            if (grid[i][j] == '@') {
                oil_fields++; // 油田数量加 1
                dfs(i, j, m, n, grid); // 调用 DFS 淹没与其相邻的所有油田格子
            }
        }
    }
    cout << oil_fields << endl; // 输出该组数据的计算结果
}

解析：此部分是二维网格连通块求解的核心控制区。两层 for 循环覆盖所有坐标。一旦触发 grid[i][j] == '@'，说明找到了新油田的某一位置。通过 DFS 蔓延清除所有相连的 @ 后，再继续寻找下一块完全独立的油田。

---