HDU 4496 D-City(并查集)

题目链接

题意:第一行输入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]都被更新成了这条链上的祖先。

Zhao Li /
Published under (CC) BY-NC-SA in categories 算法  tagged with 并查集