PAT甲题题解-1013. Battle Over Cities (25)-求联通分支个数

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题目就是求联通分支个数
删除一个点，剩下联通分支个数为cnt，那么需要建立cnt-1边才能把这cnt个联通分支个数求出来
怎么求联通分支个数呢
可以用并查集，但并查集的话复杂度是O(m*logn*k)
我这里用的是dfs，dfs的复杂度只要O((m+n)*k)
这里k是指因为有k个点要查询，每个都要求一下删除后的联通分支数。
题目没给定m的范围，所以如果m很大的话，dfs时间会比较小。

for一遍1~n个点，每次从一个未标记的点u开始dfs，标记该dfs中访问过的点。
u未标记过，说明之前dfs的时候没访问过该点，即表明该点与前面的点不属于同一个分支，相当于新的分支。
所以只要统计一下1~n中dfs多少次，就有多少个联通分支
删除的点最开始标记一下，就不会访问到了。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <vector>
#include <cstring>
using namespace std;
const int maxn=+;
int n,m,k;
int check[maxn]; //先标记哪些点会check，防止有重复的点做重复的工作
int ans[maxn]; //删掉节点i后剩余的连通分支数目
int vis[maxn]; //用于dfs时候的标记
struct Edge{
int to;
int next;
}edge[maxn*maxn];
int head[maxn];
int tot;void init(){
memset(head,-,sizeof(head));
tot=;
}
void add(int u,int v){
edge[tot].to=v;
edge[tot].next=head[u];
head[u]=tot++;
}void dfs(int u){
vis[u]=;
if(head[u]==-)
return;
for(int k=head[u];k!=-;k=edge[k].next){
int v=edge[k].to;
if(!vis[v]){
dfs(v);
}
}
}
/*
对于要check的点，求删除后的联通分支数，存储在ans数组里
*/
void solve(){
memset(ans,,sizeof(ans));
for(int i=;i<=n;i++){
//如果i是要被询问的
if(check[i]){
memset(vis,,sizeof(vis));
vis[i]=;
for(int j=;j<=n;j++){
//每次有没被访问过的节点，表明又是一个新的联通分支
if(!vis[j] && j!=i){
dfs(j);
ans[i]++;
}
}
}
}
}
int main()
{
int u,v;
init();
scanf("%d %d %d",&n,&m,&k);
for(int i=;i<m;i++){
scanf("%d %d",&u,&v);
add(u,v);
add(v,u);
}
memset(check,,sizeof(check));
vector<int>query;
for(int i=;i<k;i++){
scanf("%d",&u);
check[u]=;
query.push_back(u);
}
solve();
for(int i=;i<query.size();i++){
u=query[i];
printf("%d\n",ans[u]-);
}
return ;
}