PAT A 1013. Battle Over Cities (25)

Strokess

于 2016-10-05 16:22:41 发布

阅读量366

点赞数

分类专栏：并查集

本文链接：https://blog.csdn.net/Strokess/article/details/52739318

版权

并查集专栏收录该内容

6 篇文章

订阅专栏

本文详细介绍了如何使用并查集解决PAT A 1013问题，通过具体代码示例展示了并查集的基本操作，包括初始化、查找、合并等，并解释了如何利用这些操作来解决特定的图论问题。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

题目连接：https://www.patest.cn/contests/pat-a-practise/1013

并查集。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1010;
struct node{
	int u, v;
};
node edge[500050]; //边最多（n * (n - 1)）/ 2条 
int f[maxn], h[maxn];
int n, m, k;
void init() {
	for(int i = 0; i <= n; i++) {
		f[i] = i;
		h[i] = 0;
	}
}
int find(int x) {
	if(f[x] == x) return x;
	else return f[x] = find(f[x]);
}
void unite(int x, int y) {
	x = find(x);
	y = find(y);
	if(x != y) {
		if(h[x] < h[y]) f[x] = y;
		else {
			f[y] = x;
			if(h[x] == h[y]) h[x]++;
		}
	}
}
bool same(int x, int y) {
	return find(x) == find(y);
}
int main() {
	scanf("%d %d %d", &n, &m, &k);
	for(int i = 1; i <= m; i++) {
		scanf("%d %d", &edge[i].u, &edge[i].v);
	}
	int tmp;
	for(int i = 1; i <= k; i++) {
		init();
		int ans = 0;
		scanf("%d", &tmp);
		for(int j = 1; j <= m; j++) {
			if(edge[j].u != tmp && edge[j].v != tmp) {
				unite(edge[j].u, edge[j].v);
			}
		}
		for(int j = 1; j <= n; j++) {
			if(f[j] == j) {
				ans++;
			}
		}
		printf("%d\n", ans - 2);
	}
	return 0;
}