本题传送门
解题思路
这题与天梯赛L2-013几乎一样。
就是计算连通块的数量，这里我刚开始直接看acwing的翻译题，但是acwing上的题目擅自加了一个条件：初始时所有城市连通。然而在acwing上ac的代码
在PAT上WA了，因为PAT上没有这个条件。
攻下一座城市之后，为了让所有城市连通，只需要在每个连通块之间建立一条边，答案就是最后算出来的连通块数量减1。
有两种方法，一种是dfs，一种是并查集
这里值得注意的一点是：并查集有两种写法
if(p[x] != x) return find(p[x]);
或者
if(p[x] != x) p[x] = find(p[x]);
前者是单纯的递归，后者是路径压缩，后者在find的过程中将路中的所有点都归在了根节点之下，这样find效率更高，速度更快，前者容易超时。
ac✅️代码
算法一 ： dfs
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;vector<int> mp[1010];
bool vis[1010];
bool lost[1010];
int ans ;
int n,m,k;
void dfs(int u)
{vis[u] = true;for(int v : mp[u]){if(!vis[v] && !lost[v]){dfs(v);}}
}int cnt(int tar)
{int res = 0;for(int i = 1 ; i <= n ; i ++){if(!vis[i] && !lost[i]){res ++;dfs(i);}}memset(vis,0,sizeof vis); return res;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cin>>n>>m>>k;for(int i = 0 ; i < m ; i++){int a,b;cin>>a>>b;mp[a].push_back(b);mp[b].push_back(a);}for(int i = 0 ; i < k ; i++){ int tar; cin>>tar;vis[tar] = true;lost[tar] = true;int cnt1 = cnt(tar);lost[tar] = false;//只有一个被标记了，不必用memset，手动恢复一下就好cout<<cnt1 - 1<<endl;}return 0;
}
算法二 ： dsu
#include<iostream>
#include<algorithm>
using namespace std;const int M = 500 * 999 , N = 1010;int p[N];
struct edge{int a,b;
}e[M];//建边int find(int x)
{if( p[x] != x) p[x] = find(p[x]);//路径压缩return p[x];
}int main()
{int n,m,k;cin>>n>>m>>k;for(int i = 0 ; i < m ; i ++){cin>>e[i].a >> e[i].b;}for(int i = 0 ; i < k ; i ++){int x;cin>>x;for(int i = 1 ; i <= n ; i ++) p[i] = i;int cnt = n-1;for(int i = 0 ; i < m ; i ++){int a = e[i].a;int b = e[i].b;if( a!=x && b!=x )//跳过有x的边{int pa = find(a);int pb = find(b);//这里合并的时候可以统一让小的成为根，但是本题也没有这个必要，我们的目的只是想要知道连通块的数量if(pa != pb){cnt--;p[pa] = pb;}}}cout<<cnt - 1 <<endl;}return 0;
}