A1013

Description:

战争中，如果城市被占领，则与之相连的所有高速路失效，给出标注出所有高速路的城市地图，求需要维修的高速路数字以让剩余的城市可以连通。

举个例子，如果有三个城市，两条公路分别连接city1-city2，和city1-city3，如果city1被敌军占领，那么我们需要维修一条高速路，即city2-city3。

并查集求集合个数，高速公路数即为集合个数-1

Input:

• 每个测试一个样例。
• 每个样例第一行包含三个数字：总城市数N<100，总高速路数M，被占领的城市数K
• 接下来M行，每行描述了一条高速路，两个数字表示其链接的城市
• 城市编号从1-N
• 最后一行包含K个询问，每个询问给出一个数字代表已被占领的城市编号

Output:

• 分别输出K行给出需要维修的高速公路数

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<algorithm>
#include<map>
#include<vector>
#include<queue>
using namespace std;
const int maxn = 1e3+5;
bool check[maxn];   //用于标志当前节点所属集合是否已访问过
int fa[maxn];   //父节点
int n, m, k;
vector<int>adj[maxn];
int get(int x){ //压缩路径找父节点
    if(fa[x] == x)
        return x;
    return fa[x] = get(fa[x]);
}
void mer(int a, int b){ //合并
    a = get(a);
    b = get(b);
    if(a != b){ //非同一集合才合并
        fa[b] = a;
    }
}
void init(){    //初始化父节点及check数组
    for(int i = 0;i <= n; i++)
        fa[i] = i;
    memset(check, false, sizeof(check));
}
int main()
{
#ifdef ONLINE_JUDGE
#else
    freopen("1.txt", "r", stdin);
#endif // ONLINE_JUDGE
    scanf("%d%d%d", &n, &m, &k);
    int a, b;
    for(int i = 0; i < m; i++){
        scanf("%d%d", &a, &b);
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    int exceptPoint;
    for(int i = 0; i < k; i++){
        scanf("%d", &exceptPoint);
        init();
        for(int j = 1; j <= n; j++){ //枚举每个点
            if(j == exceptPoint) continue;  //孤岛，所有出度忽略
            for(int edge = 0; edge < adj[j].size(); edge++){
                b = adj[j][edge];
                if(b == exceptPoint) continue;//孤岛，所有入度忽略
                mer(j, b);
            }
        }
        int cnt = 0;
        for(int j = 1; j <= n; j++){
            if(j == exceptPoint) continue;  //孤岛，排斥在所有集合外，不予处理
            if(check[get(j)] == false){ //当前节点所属集合尚未访问过，即为新集合
                cnt++;
                check[get(j)] = true;
            }
        }
        printf("%d\n", cnt-1);
    }
    return 0;
}