题目描述

在战争中，所有城市都必须通过高速公路连接起来，这一点至关重要。

如果一个城市被敌人占领，则从该城市/往该城市的所有高速公路都将关闭。

此时，我们必须立即判断是否需要维修其他高速公路以保持其余城市的连通性。

给定城市与道路分布地图以及一个重点关注城市列表，请你判断，当列表中的某个城市被攻陷时，至少要维修多少条高速公路才能保持其余城市的连通性。

例如，共有 3 座城市，由 2 条高速公路将它们连通，一条连接城市 1 和城市 2，一条连接城市 1 和城市 3。

当城市 1 被敌人占领时，我们需要在城市 2 和城市 3 之间维修一条高速公路，以保持这两座城市的连通。

输入格式
第一行包含三个整数 N,M,K，分别表示城市总数，高速公路总数，重点关注城市数量。

接下来 M 行，每行包含两个整数 a,b，表示城市 a 和城市 b 之间存在一条高速公路。

所有城市编号从 1 到 N。

最后一行，包含 K 个整数，表示重点关注的城市编号。

输出格式
共 K 行，每行输出一个重点关注城市被占领时，为了保持其余城市连通性，需要维修的最少高速公路条数。

数据范围
2≤N≤1000,
1≤M≤N(N−1)2,
1≤a,b≤N,
1≤K≤N,
KM≤3500000,
数据保证最开始所有城市保持连通。

样例

输入样例:
3 2 3
1 2
1 3
1 2 3
输出样例：
1
0
0

算法1

(并查集) $O(mk)$

去掉一个点后统计连通块的数量，每一次枚举除了这个点的其余所有点
n个点最少需要n-1个点就可以联通

另外记一下define的用法

时间复杂度

参考文献

C++ 代码

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;

const int N=1010;
int p[N];
int num[N];
int n,m,k;
typedef pair<int,int>PII;
vector<PII>city;

int find(int a)
{
    if(a!=p[a])p[a]=find(p[a]);
    return p[a];
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);


    cin>>n>>m>>k;

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

    for(int i=0;i<m;i++)
    {
        int a,b;
        cin>>a>>b;
        city.push_back({a,b});
    }

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

        for(int i=1;i<=n;i++)p[i]=i;
        int cnt=n-1;
        for(int i=0;i<m;i++)
        {
            int a=city[i].fi,b=city[i].se;
            if(a!=c&&b!=c)
            {
                a=find(a),b=find(b);
                if(a!=b)
                {
                    p[a]=b;
                    cnt--;
                }
            }
        }
        cout<<cnt-1<<endl;

    }
    return 0;
}