题目
解决
思路
思路：
本题最重要的是要认识到，恢复点的连通，其实只需要让不连通的连通子图之间变成连通即可，也就是说只需要增加”连通图的数量-1“条边，得到的就是答案 计算连通子图的数量：
思路一：DFS
单次DFS访问的是单个连通子图，所以只需要计数运行了多少次DFS即可。 思路二： 并查集
将一个连通子图认为是一个集合，只需要计算去掉检查的结点之后的集合数量即可。判断图每条边的两个顶点是不是在同一个集合例面，如果在同一个集合，不处理，否则将两个顶点加入同一个集合。注意：
在做并集的时候，要跳过checkPoint，代表这个点被删除了。在为根结点打标时，同样要跳过checkPoint，因为初始化时所有结点都被初始化为自己的根结点，在打标过程isRoot[findFather(i)] = true,会将isRoot[checkPoint]赋为true
实现
Code1(DFS)
#include<cstdio>
#include<vector>
using namespace std;
const int maxn = 1010;
vector<int> G[maxn];
bool vis[maxn] = {false};
int checkPoint;
void DFS(int v){
if(v == checkPoint){
return;
}
vis[v] = true;
for(int i=0; i<G[v].size(); i++){
if(vis[G[v][i]] == false){
DFS(G[v][i]);
}
}
}
void visInit(){
for(int i=0; i<maxn; i++){
vis[i] = false;
}
}
int n, m, k;
int main(){
scanf("%d%d%d", &n, &m, &k);
int a, b;
for(int i=0; i<m; i++){
scanf("%d%d", &a, &b);
G[a].push_back(b);
G[b].push_back(a);
}
for(int i=0; i<k; i++){
scanf("%d", &checkPoint);
visInit();
int ans = 0;
for(int j=1; j<=n; j++){
if(j != checkPoint && vis[j] == false){
DFS(j);
ans++;
}
}
printf("%d\n", ans-1);
}
return 0;
}
Code2(DSU)
#include<cstdio>
#include<vector>
using namespace std;
const int N = 1010;
vector<int> G[N];
int father[N];
bool isRoot[N] = {false};
int n, m, k;
int checkPoint;
int findFather(int x){
int a = x;
while(x != father[x]){
x = father[x];
}
while(a != father[a]){
int z = a;
a = father[a];
father[z] = x;
}
return x;
}
void init(){
for(int i=1; i<=n; i++){
father[i] = i;
isRoot[i] = false;
}
}
void Union(int a, int b){
int faA = findFather(a);
int faB = findFather(b);
if(faA != faB){
father[faA] = faB;
}
}
int main(){
scanf("%d%d%d", &n, &m, &k);
int a, b;
for(int i=0; i<m; i++){
scanf("%d%d", &a, &b);
G[a].push_back(b);
G[b].push_back(a);
}
for(int q=0; q<k; q++){
scanf("%d", &checkPoint);
init();
for(int i=1; i<=n; i++){
for(int j=0; j<G[i].size(); j++){
int u = i;
int v = G[i][j];
if(u == checkPoint || v == checkPoint) continue;
Union(u, v);
}
}
for(int i=1; i<=n; i++){
if(i == checkPoint) continue;
isRoot[findFather(i)] = true;
}
int ans = 0;
for(int i=1; i<=n; i++){
if(isRoot[i] == true){
ans++;
}
}
printf("%d\n", ans-1);
}
return 0;
}
