hdu 4496 D-City(並查集)

題目鏈接：hdu 4496 D-City

題目大意：給出一張圖，按照給定邊的順序逐個刪除，問沒刪除一條之後的聯通塊數量。

解題思路：逆向並查集求聯通分量，假設一開始各個城市都不連通，然後從最後一條邊開始添加，如果新添加的邊聯通了兩個聯通塊，那麼聯通分量就要減1，最後在正序輸出即可。

#include 
#include 

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;
}