AcWing 1485. 战争中的城市 DFS---连通块判断
原题链接
中等
作者:
吃饱喝足不学习
,
2022-02-25 20:00:33
,
所有人可见
,
阅读 273
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010,M = N*N;
int n,m,k,a,b,c,res;
int h[N],e[M],ne[M],idx;
bool f[N];
void add(int a,int b)
{
e[++idx]=b;
ne[idx]=h[a];
h[a]=idx;
}
void dfs(int x)
{
f[x]=true;
for(int i=h[x];i;i=ne[i])
{
int y=e[i];
if(y==c || f[y])
continue;
else
dfs(y);
}
}
int main()
{
cin>>n>>m>>k;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&a,&b); // 存图,无向图存两次
add(a, b);
add(b, a);
}
while(k--)
{
res=0;
cin>>c; //城市c被攻陷,判断不含城市c的连通块数量
memset(f,false,sizeof f);
for(int i=1;i<=n;i++)
{
if(i==c)
continue;
if(!f[i]) // 发现了新的连通块
{
res++;
dfs(i);
}
}
cout<<res-1<<endl;
}
return 0;
}