hdu 4496 D-City(并查集)

题目链接：hdu 4496 D-City

题目大意：给出一张图，按照给定边的顺序逐个删除，问没删除一条之后的联通块数量。

解题思路：逆向并查集求联通分量，假设一开始各个城市都不连通，然后从最后一条边开始添加，如果新添加的边联通了两个联通块，那么联通分量就要减1，最后在正序输出即可。

#include <cstdio>
#include <cstring>

const int N = 10005;
const int M = 100005;

int n, m, ans[M];
int f[N], x[M], y[M];

int getfar(int s) {
	return s == f[s] ? s : f[s] = getfar(f[s]);
}

void init () {
	for (int i = 0; i < n; i++)
		f[i] = i;

	for (int i = 0; i < m; i++)
		scanf("%d%d", &x[i], &y[i]);
}

void solve () {
	int tmp = n;
	for (int i = m - 1; i >= 0; i--) {
		ans[i] = tmp;

		int p = getfar(x[i]);
		int q = getfar(y[i]);

		if (p != q) {
			f[q] = p;
			tmp--;
		}
	}

	for (int i = 0; i < m; i++)
		printf("%d\n", ans[i]);
}

int main () {
	while (scanf("%d%d", &n, &m) == 2) {
		init();
		solve();
	}
	return 0;
}

hdu 4496 D-City(并查集),布布扣,bubuko.com

hdu 4496 D-City(并查集)

原文：http://blog.csdn.net/keshuai19940722/article/details/24499129