PAT 1013. Battle Over Cities
原题链接
中等
这个题目的标准做法应该是使用图论的连通分量吧, 但是我这里是使用的并查集来模拟的 效率自然是不高的, 但是这里的n是小于1000的, 所有也是没有任何问题的.
/*
* Author: Apprentice_lb
* Created Time: 2022/2/24 12:08:20
* File Name: pat.cpp
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<string>
#include<cassert>
using namespace std;
const int N = 1000 + 10;
int n, m, k;
struct Node{
int l, r;
}a[N * N];
int query[N];
int res[N], fa[N];
int get(int x){
if(fa[x] == x) return x;
return fa[x] = get(fa[x]);
}
int main() {
cin >> n >> m >> k;
for(int i = 1; i <= m; i++) cin >> a[i].l >> a[i].r;
for(int i = 1; i <= k; i++) cin >> query[i];
for(int i = 1; i <= k; i++){
memset(fa, 0, sizeof fa);
for(int j = 1; j <= n; j++) fa[j] = j;
fa[query[i]] = 0;
for(int j = 1; j <= m; j++){
int x = a[j].l, y = a[j].r;
if(x == query[i] || y == query[i]) continue;
fa[get(x)] = get(y);
}
memset(res, 0, sizeof res);
for(int j = 1; j <= n; j++) res[get(j)] = 1;
int ans = 0;
for(int j = 1; j <= n; j++)
if(res[j] == 1) ans++;
cout << ans - 1 << '\n';
}
return 0;
}