题目描述
在战争中,所有城市都必须通过高速公路连接起来,这一点至关重要。
如果一个城市被敌人占领,则从该城市/往该城市的所有高速公路都将关闭。
此时,我们必须立即判断是否需要维修其他高速公路以保持其余城市的连通性。
给定城市与道路分布地图以及一个重点关注城市列表,请你判断,
当列表中的某个城市被攻陷时,至少要维修多少条高速公路才能保持其余城市的连通性。
例如,共有 3 座城市,由 2 条高速公路将它们连通,一条连接城市 1 和城市 2,一条连接城市 1 和城市 3。
当城市 1 被敌人占领时,我们需要在城市 2 和城市 3 之间维修一条高速公路,以保持这两座城市的连通。
输入格式
第一行包含三个整数 N,M,K,分别表示城市总数,高速公路总数,重点关注城市数量。
接下来 M 行,每行包含两个整数 a,b,表示城市 a 和城市 b 之间存在一条高速公路。
所有城市编号从 1 到 N。
最后一行,包含 K 个整数,表示重点关注的城市编号。
输出格式
共 K 行,每行输出一个重点关注城市被占领时,为了保持其余城市连通性,需要维修的最少高速公路条数。
数据范围
2≤N≤1000,
1≤M≤N(N−1)2,
1≤a,b≤N,
1≤K≤N,
KM≤3500000,
数据保证最开始所有城市保持连通。
输入样例:
3 2 3
1 2
1 3
1 2 3
输出样例:
1
0
0
算法1
本题目本来是考核并查集的使用
但是由于数据规模适中,使用深度优先搜索DFS 也是OK的
去掉题意中被占领的那座城市 看看进行几次DFS搜索能遍历完全部图中的城市节点
那么就是答案
图示
C++ 代码
#include <iostream>
#include <vector>
#include <memory.h>
using namespace std;
const int N = 1010;
vector<int> graph[N];
int vis[N];
int lost,ans;
int n,m,k;
int a,b;
void dfs(int x){
vis[x]=1;
int size = graph[x].size();
for(int i =0;i < size;i++){
int p = graph[x][i];
if(vis[p]==0 && p!=lost){
dfs(p);
}
}
}
void solve(){
ans =0;
memset(vis,0,sizeof vis);
for(int i = 1;i<=n;i++){
if(i!=lost && vis[i] ==0){
ans++; dfs(i);
}
}
printf("%d\n",ans-1);
return ;
}
int main(){
scanf("%d%d%d",&n,&m,&k);
for(int i = 1; i <= m;i++){
scanf("%d%d",&a,&b);
graph[a].push_back(b);
graph[b].push_back(a);
}
for(int i =1;i<=k;i++){
scanf("%d",&lost);
solve();
}
return 0;
}
最后一幅图应该搜索四次把
吓得我赶紧去acwing和pat重新提交了一次。没错啊。
ans-1 是因为 有的从0开始 有的从1开始,最后打印做了调整吧
作图中可能做了一些调整,以ac代码为准吧
hh我刚才自己做的时候 并完全完全恢复vis,导致上一次删除的点没有被保存,所以错了。如果保存上一个点的话是不用ans-1的感谢回复
为什么要返回ans -1 啊,