题目：PTA L2-013 红色警报 题解
题目描述
战争中需要监控城市连通性，当失去某个城市导致连通块数量增加时触发红色警报。具体要求见题目链接。
[L2-013 红色警报](https://ykj.cpolar.cn/problem/8600)
解题思路
核心逻辑：
每次攻占一个城市后，判断剩余城市的连通块数量是否增加。若增加，则发出警报。需注意以下两点：
1. 初始不连通的情况：若原图已分裂为多个连通块，但攻占后连通性未改变（如攻占孤立城市），则不触发警报。
2. 动态维护：需高效处理城市攻占后的连通性变化，避免重复计算。
方法一：DFS + 邻接矩阵
实现步骤
1. 邻接矩阵存储：用二维数组 g[N][N] 记录城市间道路，确保去重。
2. 连通块计算：每次攻占后，通过 DFS 遍历未被攻占的城市，统计连通块数。
3. 删除操作：直接清空邻接矩阵中与被攻占城市相关的所有边。
代码亮点
void dfs(int x) {
for (int i = 0; i < n; i++) {
if (!vis[i] && g[x][i] && !suv[i]) {
vis[i] = 1;
dfs(i);
}
}
}
时间复杂度：O(k·n²)，适合小规模数据。 适用场景：实现简单，适合邻接矩阵的静态图。
方法二：BFS + 邻接矩阵
实现步骤
1. 连通块计算：用 队列 替代递归，避免栈溢出风险。
2. 动态更新：与DFS类似，但更适合层序遍历。
代码亮点
void bfs(int x) {
queue<int> q;
q.push(x);
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v = 0; v < n; v++) {
if (g[u][v] && !vis[v] && !suv[v]) {
vis[v] = 1;
q.push(v);
}
}
}
}
时间复杂度：与方法一相同，但空间占用略高。 优势：非递归实现，适合大规模图的层序遍历。
方法三：并查集 (DSU) + 邻接矩阵
实现步骤
1. 离线处理：攻占城市后，重新构建并查集。
2. 连通块统计：通过父节点查询根节点，统计独立连通块数。
代码亮点
int cal() {
init();
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (g[i][j] && !vis[i] && !vis[j])
merge(i, j);
int res = 0;
for (int i = 0; i < n; i++)
if (fa[i] == i && !vis[i]) res++;
return res;
}
时间复杂度：O(k·n²)，但实际合并操作接近常数时间。 优势：动态合并效率高，适合频繁查询连通性的场景。
方法对比
方法 优点 缺点 DFS/BFS 实现简单，逻辑清晰 重复遍历导致效率较低 并查集 动态维护高效，适合多次查询 需离线处理，代码复杂度高
复杂度总结
DFS/BFS：适合小规模数据（n ≤ 500），代码简洁。 DSU：理论上更高效，但需注意攻占后的并查集重建开销。
关键注意事项
1. 删除城市的影响：需同时清除邻接矩阵中的双向边（方法一、二）或标记为攻占状态（方法三）。
2. 初始连通块计算：无论原图是否连通，均需先统计初始连通块数。
3. Game Over条件：所有城市被攻占时需立即终止程序。
总结
三种方法均能通过题目测试，选择依据如下：
1. 推荐DFS/BFS：快速实现，适合竞赛场景。
2. 并查集优化：若需处理动态连通性问题（如恢复城市），可参考离线处理策略。
完整代码请参考我的提交记录:
[DFS+邻接矩阵](https://ykj.cpolar.cn/submission/602080)
[BFS+邻接矩阵](https://ykj.cpolar.cn/submission/602081)
[并查集+邻接矩阵](https://ykj.cpolar.cn/submission/602079)