题目链接：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; }