HDU 4496 D-City（并查集）

November 27, 2015

题目链接

题意：第一行输入 N（0 < N <= 10000 ）和 M（0 < M <= 100000 ）分别代表节点数和边数，接下来 M 行每行有两个数 u 和 v（0 <= u, v < N）代表 u 和 v 两点间有边连接。输出 M 行，输出删掉前 i 个边时的连通块。

解法：用并查集从后往前加边。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;
const int N = 10010;
const int M = 100010;
int n,m;
int ans[M], fa[N];

struct node{
    int u,v;
}edge[M];

//找最终祖先
int findfa(int x){
    if(fa[x] != x)
        fa[x] = findfa(fa[x]);
    return fa[x];
}

int main()
{
    freopen("a.txt", "r", stdin);
    while(scanf("%d %d", &n, &m) != EOF){
        memset(ans, 0, sizeof(ans));
        memset(edge, 0, sizeof(edge));
        //预处理
        for(int i = 0; i < n; i++)
            fa[i] = i;
        for(int i = 0; i < m; i++)
            scanf("%d %d", &edge[i].u, &edge[i].v);
        int sum = n;
        for(int i = m-1; i >= 0; i--){
            ans[i] = sum;
            //合并
            int xx = findfa(edge[i].u);
            int yy = findfa(edge[i].v);
            if(xx != yy){
                sum--;
                fa[xx] = yy;
            }
        }
        for(int i = 0; i < m; i++)
            printf("%dn", ans[i]);
    }
    return 0;
}

并查集分为三部分：预处理、找祖先、合并。

在 findfa 函数中使用了路径压缩：findfa 函数中的 return 可以在回溯时压缩路径，也就是说当我们从一条链上的最后一个节点往上找到祖先后，这条链上所有的点 i 的 fa[i]都被更新成了这条链上的祖先。