【数据结构】图-红色警报
题目描述
战争中保持各个城市间的连通性非常重要。本题要求你编写一个报警程序，当失去一个城市导致国家被分裂为多个无法连通的区域时，就发出红色警报。注意：若该国本来就不完全连通，是分裂的k个区域，而失去一个城市并不改变其他城市之间的连通性，则不要发出警报。
输入
输入在第一行给出两个整数N（0 < N ≤ 500）和M（≤ 5000），分别为城市个数（于是默认城市从0到N-1编号）和连接两城市的通路条数。随后M行，每行给出一条通路所连接的两个城市的编号，其间以1个空格分隔。在城市信息之后给出被攻占的信息，即一个正整数K和随后的K个被攻占的城市的编号。
注意：输入保证给出的被攻占的城市编号都是合法的且无重复，但并不保证给出的通路没有重复。
输出
对每个被攻占的城市，如果它会改变整个国家的连通性，则输出Red Alert: City k is lost!，其中k是该城市的编号；否则只输出City k is lost.即可。如果该国失去了最后一个城市，则增加一行输出Game Over.。
输入样例1
5 4 0 1 1 3 3 0 0 4 5 1 2 0 4 3
输出样例1
City 1 is lost. City 2 is lost. Red Alert: City 0 is lost! City 4 is lost. City 3 is lost. Game Over.
思路分析
首先我们需要计算出每次的联通分量数目：
建立邻接矩阵，用DFS的方式遍历图，如果只需要从一个节点出发就能遍历所有节点，那么只有一个联通分量，如果需要从多个节点出发才能遍历完所有节点，那么有多个联通分量。
因此，解决方式就是，从所有节点出发DFS，每遍历一个节点就标记下来，即不会遍历已遍历的节点，那么联通分量的数目就是需要DFS节点的数目。
然后每失去一个城市，联通分量至少增加一个或者减少一个，如果只增加一个，说明该城市的失去没有破坏其他城市的联通性，如果减少一个，说明该城市本来就是和他们不联通的，如果增加多个，那么说明该城市的失去破坏了其他城市的联通性，这就是我们要求的。
AC代码
#include<iostream>
using namespace std;
const int MaxLength = 100;
class Map {
bool visited[MaxLength] = {false};
int matrix[MaxLength][MaxLength] = {0};
int vertexNumber,edgeNumber;
int connectedComponent = 0, tempCount,loss=0;
public:
Map() {
connectedComponent = 0;
cin >> vertexNumber >> edgeNumber;
for (int i = 0; i < edgeNumber; i++) {
int tail, head;
cin >> tail >> head;
matrix[tail][head] = matrix[head][tail] = 1;
}
Check();
}
void Attacked() {
int t;
cin>>t;
while(t--){
loss++;
int gone;
cin>>gone;
int last=connectedComponent;
for(int i=0;i<vertexNumber;i++)
matrix[i][gone]=matrix[gone][i]=0;
Check();
if(last+1<connectedComponent)
cout<<"Red Alert: City "<<gone<<" is lost!"<<endl;
else cout<<"City "<<gone<<" is lost."<<endl;
if(loss==vertexNumber)
cout<<"Game Over."<<endl;
}
}
void DFS(int current) {
if (visited[current])
return;
visited[current] = true;
tempCount++;
for (int i = 0; i < vertexNumber; i++)
if (matrix[current][i])
DFS(i);
}
void Check(){
connectedComponent=0;
for(int i=0;i<vertexNumber;i++)
visited[i]= false;
for (int i = 0; i < vertexNumber; i++) {
tempCount = 0;
if(!visited[i])
DFS(i);
if (tempCount>=1)
connectedComponent++;
}
}
};
int main() {
Map test;
test.Attacked();
}腾讯云开发者
