1013 Battle Over Cities (25 分) 【难度: 中 / 知识点: 连通块】

https://pintia.cn/problem-sets/994805342720868352/problems/994805500414115840

将这些连通块，连接起来最少的边，即是答案。
将n个点连接，最少需要(n-1)条边，故本题答案即为连通块的数量-1

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
vector<int>ve[N];
int n,m,k,st[N];
void dfs(int u)
{
    st[u]=1;
    for(int i=0;i<ve[u].size();i++) if(!st[ve[u][i]]) dfs(ve[u][i]);
}
int main(void)
{
    cin>>n>>m>>k;
    for(int i=0;i<m;i++)
    {
        int a,b; cin>>a>>b;
        ve[a].push_back(b);
        ve[b].push_back(a);
    }
    for(int i=0;i<k;i++)
    {
        memset(st,0,sizeof st);
        int s; cin>>s;
        st[s]=1;//将选的点，提前标记
        int cnt=0;
        for(int i=1;i<=n;i++) 
        {
            if(!st[i]) cnt++,dfs(i);
        }
        cout<<cnt-1<<endl;
    }
    return 0;
}