题目描述

求一个有环连通图在去掉某一个（可以使多个）节点及其相关的边之后，剩余多少个连通块

由于该连通图带环，所以不能使用带权值的并查集（每一个节点的度）

所以使用逆向的方式，直接将与x相关的边去掉，不用于建立并查集

算法1

C++ 代码

#include<iostream>
using namespace std;
const int N=1010;
const int M=(N-1)*N/2;
int f[N];

struct edge{
    int a,b;
}e[M];

int find(int x){
    if(x!=f[x]){
        f[x]=find(f[x]);
    }
    return f[x];
}

void merge(int a,int b){
    f[a]=b;
}

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;
        int cnt=n;//初始时有n个连通块
        //初始化并查集
        for(int j=1;j<=n;j++){
            f[j]=j;
        }

        for(int j=0;j<m;j++){
            int  u=e[j].a,v=e[j].b;
            if(u!=x&&v!=x){
                //加入与x无关的边
                u=find(u);v=find(v);
                if(u!=v){
                    merge(u,v);
                    cnt--;//每个并一个连通块,连通块个数减1
                }
            }
        }
        cout<<cnt-2<<endl;
    }

    return 0;
}