题目
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 city?1?? -city?2?? and city?1?? -city?3?? . Then if city?1 is occupied by the enemy, we must have 1 highway repaired, that is the highway city?2?? -city?3.
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个节点只需要n-1条边
下一步就是求连通分量数。
- 按顺序遍历图中每个节点
- 若节点未被遍历过，则以该点为起点，进行深度\广度优先遍历，并标记每个遍历过的点。
- 遍历结束后，即求得一个连通分量。
顺序遍历结束后，就求得了整张图的连通分量数。
对于去掉一点求连通分量，是否需要特殊标记该点？
答案是不需要，只需要将该点标记为已遍历过即可。在遍历时，首先会检查要遍历的点是否被遍历过，若被遍历过则不会进行遍历，若某个点从开始就被标记已遍历，则该点从始到终都不会被遍历，满足该点被去掉的情况。
#include <stdio.h>
#include <stack>
using namespace std;
int main(){int n,m,k,i,c1,c2 ,j,kk,count,now;if(3 != scanf("%d %d %d",&n,&m,&k))return -2;int city[n+1][n+1] ={0};int visit[n+1];for(i=0;i<m;i++){if(2 != scanf("%d %d",&c1 ,&c2))return -2;city[c1][c2] = 1;city[c2][c1] =1;}for(i=0;i<k;i++){if(1 != scanf("%d",&c1))return -2;for(j=0;j<n+1;j++){visit[j]=0;}count = 0;visit[c1] = 1;for(j=1;j<n+1;j++){ if(!visit[j]){// 深度优先遍历stack<int> s ;s.push(j);now = j; while(!s.empty()){now = s.top();s.pop();visit[now] = 1;for(kk=1;kk<n+1;kk++){if(city[now][kk] &&!visit[kk]){now = kk;s.push(now);break;}}} count++;} }printf("%d",count-1);if(i!=k-1){printf("\n");}}return 0;
}