法1:并查集

//等价于如果删掉某一点的话，看一下剩余连通子图的数量-1
//即要加多少边可以使所有连通子图都连在一起
#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 1010,M = 500010;

int n,m,k;
int p[N];

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

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

int main()
{
    cin>>n>>m>>k;

    for(int i = 0; i<m; i++) cin>>e[i].a>>e[i].b;

    while(k--)
    {
        int x;
        cin>>x;

        for(int i = 1; i<=n; i++) p[i] = i;

        int cnt = n-1;//当前的点删掉，剩下n-1个点，即刚开始有n-1个连通子图

        for(int i = 0; i<m; i++)//枚举一下所有边
        {
            int a = e[i].a,b = e[i].b;
            if(a!=x &&b!=x)
            {
                int pa = find(a),pb = find(b);
                if(pa!=pb)//还有连通
                {
                    p[pa] = pb;//连通
                    cnt--;
                }
            }
        }
        cout<<cnt-1<<endl;
    }   
    return 0;
}

法2:DFS

//连通子图数量-1
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>

using namespace std;

int n,m,k,lost;
vector<int> v[1010];
bool st[1010];
void dfs(int u)
{
    st[u] = 1;//标记
    for(auto i:v[u])//遍历其连通结点
    {
        if(!st[i]) dfs(i);
    }
}

int main()
{
    cin>>n>>m>>k;
    int a,b;
    while(m--)
    {
        cin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }

    for(int i = 0; i<k; i++)
    {
        memset(st,0,sizeof st);
        cin>>lost;
        st[lost] = 1;
        int cnt = 0;
        for(int j = 1; j<=n; j++)
        {
            if(!st[j])
            {
                 dfs(j);//如果没有标记过，则寻找其连通的节点让其标记
                 cnt++;//连通子图数量
            }
        }
        cout<<cnt-1<<endl;
    }
}