【并查集】hdu4496

D-City

Problem Description
Luxer is a really bad guy. He destroys everything he met. 
One day Luxer went to D-city. D-city has N D-points and M D-lines. Each D-line connects exactly two D-points. Luxer will destroy all the D-lines. The mayor of D-city wants to know how many connected blocks of D-city left after Luxer destroying the first K D-lines in the input. 
Two points are in the same connected blocks if and only if they connect to each other directly or indirectly.
 

Input
First line of the input contains two integers N and M. 
Then following M lines each containing 2 space-separated integers u and v, which denotes an D-line. 
Constraints: 
0 < N <= 10000 
0 < M <= 100000 
0 <= u, v < N. 
 

Output
Output M lines, the ith line is the answer after deleting the first i edges in the input.
 

Sample Input
5 10 0 1 1 2 1 3 1 4 0 2 2 3 0 4 0 3 3 4 2 4
 

Sample Output
1 1 1 2 2 2 2 3 4 5
Hint
The graph given in sample input is a complete graph, that each pair of vertex has an edge connecting them, so there's only 1 connected block at first. The first 3 lines of output are 1s because after deleting the first 3 edges of the graph, all vertexes still connected together. But after deleting the first 4 edges of the graph, vertex 1 will be disconnected with other vertex, and it became an independent connected block. Continue deleting edges the disconnected blocks increased and f vertex, so the last output should always be N.
 
 
一条一条边的删除是不科学的,但是可以倒过来——从最后一条边开始把每条边一一加入到图中,如果该条边是在某两个联通块之间就说明联通块的个数会在此之后减少1,否则个数不变(一条边都没加的时候联通块数等于点的数目),然后再反向输出就好了!这个显然是用并查集实现!
注意点是从零开始的(我最开始数组清零的时候是从1开始的(读题不认真啊 敲打,没有观察数据啊 敲打),囧……)
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
long  t;
long  n, m;
long  f[10010];
long  re[100100], a[100100], b[100100];
long find(long x)
{
    if (f[x] == x) return x;
    f[x] = find(f[x]);
    return(f[x]);
}
void merge(long x, long y)
{
    x = find(f[x]);
    f[x] = find (y);
}


int main()
{
    //freopen("D.in", "r", stdin);

    while(scanf("%d%d", &n, &m) == 2)
    {
        for (long i=1; i<=m; i++)
        {
            scanf("%d%d", &a[i], &b[i]);
        }
        for (long i = 0; i <= n-1; i++)
            f[i]=i;
        re[m]=n;
        for(long i = m; i >= 1; i--)
        {
            if (find(a[i]) != find(b[i]))
            {
                re[i-1] = re[i] -1;
                merge(a[i], b[i]);
            }
            else re[i-1] = re[i];

        }
        for(long i=1; i<=m; i++)
        {
            printf("%d\n",re[i]);
        }
    }
    return 0;
}



全部评论

相关推荐

点赞 评论 收藏
分享
代码飞升:别用口语,后端就写后端,前端就写前端,最后别光后悔
点赞 评论 收藏
分享
小浪_Coding:找硬件测试,也可兼顾软测欧, 简历还可以的 ,注意排版,项目写的有条理一点, 然后个人技能多加点, 润色好简历之后就开始沟通海投了,深圳,东莞这边做硬件相关的公司还不少, 医疗类,仪器类的都可以尝试
点赞 评论 收藏
分享
07-17 11:27
门头沟学院 Java
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务