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.
例如，如果我们有3个城市和2个高速公路连接城市1到城市2和城市1到城市3，然后如果城市1被敌人占领，这时我们必须把1条公路修好，他就是从城市2到城市3的公路。
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.
每个输入文件包含一个测试用例。每个案例都包含3个数字N（<1000）M和K，分别是城市总数，剩余高速公路数量和要检查的城市数量。然后接下来是M行，每行描述一个2个整数的高速公路，这是高速公路连接的城市数量。城市的编号从1到N。最后有一行包含K数字，代表我们关心的城市。
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
对于每一个 K城市，如果该城市失守，输出需要修复高速公路的数量。
3 2 3
1 2
1 3
1 2 3
Sample Output:
1
0
0
样例解释： 有3个城市，2条路线，3个城市都要检查
1 2 代表城市1和城市2之间有一条路；
1 3代表城市1和城市3之间有一条路；
输入要检查的三个城市；
第一个城市被攻占，1和2,1和3两条路都断，要使剩下的2,3保持联通，需要一条路把他们连起来；
第二个，第三个城市被攻占，他们都始终有一条路和1相连，不需要连了
添加的最少的路线，就是他们的连通分量数-1，因为当a个互相分立的连通分量需要变为连通图的时候，只需要添加a-1个路线，就能让他们相连。所以这道题就是求去除了某个结点之后其他的图所拥有的连通分量数。
参考>>>>>>>https://blog.csdn.net/whl_program/article/details/77627856
#include<iostream>
#include<algorithm>///fill函数
using namespace std;
int v[1000][1000],n;///二维矩阵存储图
bool visit[1000];///记录是否遍历
void dfs(int node)
{///dfs搜索节点
visit[node]=true;
for(int i=1; i<=n; i++)
{
if(visit[i]==false&&v[node][i]==1)
dfs(i);
}
}
int main()
{
int m,k,a,b;
cin>>n>>m>>k;
for(int i=0; i<m; i++)
{///m为路径数
cin>>a>>b;
v[a][b]=v[b][a]=1;
}///无向连通设置初始距离均为1
for(int i=0; i<k; i++)
{///k次搜索
fill(visit,visit+1000, false);
///每进行一次搜索就将visit数组全部置false（未遍历）
cin>>a;///被攻占的城市
int cnt=0;///用于记录连通分量个数
visit[a]=true;///标记被攻占的
for(int j=1; j<=n; j++)
{///城市名称从1开始
if(visit[j]==false)
{///找剩余节点
dfs(j);
cnt++;
}
}
cout<<cnt-1<<endl;
///连通分量数减一即为连通线的数量
}
}
| 
转播
