1013 Battle Over Cities (25分)
It is vitally important to have all the cities connected by highways in a war. If a city is occupied by the enemy, all the highways from/toward that city are closed. We must know immediately if we need to repair any other highways to keep the rest of the cities connected. Given the map of cities which have all the remaining highways marked, you are supposed to tell the number of highways need to be repaired, quickly.
For example, if we have 3 cities and 2 highways connecting city1-city2 and city1-city3. Then if city1 is occupied by the enemy, we must have 1 highway repaired, that is the highway city2-city3.
Input Specification:
Each input file contains one test case. Each case starts with a line containing 3 numbers N (<1000), M and K, which are the total number of cities, the number of remaining highways, and the number of cities to be checked, respectively. Then M lines follow, each describes a highway by 2 integers, which are the numbers of the cities the highway connects. The cities are numbered from 1 to N. Finally there is a line containing K numbers, which represent the cities we concern.
Output Specification:
For each of the K cities, output in a line the number of highways need to be repaired if that city is lost.
Sample Input:
3 2 3
1 2
1 3
1 2 3
Sample Output:
1
0
0
题目大意:输入N,K,M三个数，N代表城市数（<1000）,K表示有几条路，接下来K行，每行表示两个城市间连通，M个测试城市（从1到N），每个数字表示如果城市被攻陷。输出城市被攻陷的话需要添加最少路,使其他城市连通。
思路：该题就是如果城市被攻陷后添加最少的路线使其他城市连通，就是找除去该城市后，所剩城市构成了几个极大连通子图，需要添加的路线就是极大连通子图数目-1，可以用图的深度优先遍历来实现。只是每次遍历前将自身设置为已访问即可。
#include<iostream>
using namespace std;
int v[1010][1010];
bool vist[1010];//图的深度优先遍历辅助数组。
int N;
int main(){
void dfs(int node);
int M,K,a,b;
scanf("%d%d%d",&N,&M,&K);//用cin最后一个测试用例会超时。
for(int i=0;i<M;++i){
scanf("%d%d",&a,&b);
v[a][b] = v[b][a] = 1;//无向图，邻接矩阵表示法。
}
int count;//用来记录图有几个极大连通子图。
for(int i=0;i<K;++i){//每个输入的数据是独立计算的。
count = 0;
scanf("%d",&a);
fill(vist,vist+1010,false);//将visit初始化为false。
vist[a] = true;//当前节点舍弃。
for(int i=1;i<=N;++i){//每个点的极大连通子图都要算。
if(vist[i]==false){//如果该节点没有被访问。
dfs(i);
++count;
}
}
printf("%d\n",count-1);
}
}
//图的深度优先遍历
//这个函数会将图的某一个节点的所有连通节点都访问。即该节点的极大连通子图。
void dfs(int node){
vist[node] = true;
for(int i=1;i<=N;++i){
if(vist[i]==false&&v[node][i]==1){
dfs(i);
}
}
}
网友评论