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 connectingcity1-city2andcity1-city3. Then ifcity1is occupied by the enemy, we must have 1 highway repaired, that is the highwaycity2-city3.

Input Specification:

Each input file contains one test case. Each case starts with a line containing 3 numbersN(<1000),MandK, which are the total number of cities, the number of remaining highways, and the number of cities to be checked, respectively. ThenMlines follow, each describes a highway by 2 integers, which are the numbers of the cities the highway connects. The cities are numbered from 1 toN. Finally there is a line containingKnumbers, which represent the cities we concern.

Output Specification:

For each of theKcities, 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个联通分量需要n-1.边缘联通，所以你可以通过计算多少个联通重量来知道几个边缘。计算多个联通重量时，可以使用深度遍历算法。

代码

//n需要个联通分量n-1条边，算多少联通重量就知道几条边。 #include <bits/stdc  .h> using namespace std; #define max 1000 int edge[max][max]; bool visited[max]; int cities; void dfs(int x){     visited[x]=1;     for(int i=1;i<=cities;i  )         if(visited[i]==0&&edge[x][i]==1) dfs(i); } int main(){     int highways,concerns,node1,node2,nocity,part=0;     scanf("%d%d%d",&cities,&highways,&concerns);     for(int i=0;i<highways;i  ){         scanf("%d%d",&node1,&node2);         getchar();         edge[node1][node2]=edge[node2][node1]=1;     }     for(int i=0;i<concerns;i  ){         part=0;         scanf("%d",&nocity);         fill(visited 1,visited cities 1,0);         visited[nocity]=1;         for(int j=1;j<=cities;j  ){             if(visited[j]==0){                 dfs(j);                 part  ;             }         }         if(part==0){             printf("0\n");         }else{             printf("%d\n",part-1);         }     }     return 0; }

总结

方法

这里用visited[i]为了记录I城市是否有记录，需要注意相关信息for循环要从i=1开始计算，但迭代器的处理需要从第二个指针开始，处理到容量 1位。

fill(visited 1,visited cities 1,0);