hdu2473junk-mailfilter(并查集的删除操作)

关键词：

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <queue>
#include <map>
#include <set>
#include <algorithm>

using namespace std;
int bin[2100000], _hash[2100000], d[2100000];
int find1(int x)
{
    return bin[x]==d[x]?d[x]:bin[x]=find1(bin[x]);
}
void join(int x, int y)
{
    int f1=find1(x);
    int f2=find1(y);
    if(f1!=f2)
        bin[f2]=f1;
}
int main()
{
    int n, m, i, cnt, num=0, sum, a, b;
    char c;
    while(scanf("%d%d",&n,&m)!=EOF&&n+m)
    {
        num++;
        sum=0;
        cnt=n;
        for(i=0; i<2000000; i++)
        {
            bin[i]=i;
            d[i]=i;
        }
        while(m--)
        {
            getchar();
            scanf("%c",&c);
            if(c=='M')
            {
                scanf("%d%d",&a,&b);
                join(a,b);
            }
            else
            {
                scanf("%d",&a);
                bin[a]=cnt;
                d[a]=cnt++;
            }
        }
        memset(_hash,0,sizeof(_hash));
        for(i=0; i<n; i++)
        {
            a=find1(d[i]);
            if(!_hash[a])
            {
                sum++;
                _hash[a]=1;
            }
            //printf("%d ",a);
        }
        //puts("");
        printf("Case #%d: %d
",num,sum);
    }
    return 0;
}

hdu2473junk-mailfilter删点并查集

删点并查集，就是用一个新的点标取代之前的点标就可以。。y一下就能够了#include<cstdio>#include<iostream>#include<algorithm>#include<string.h>#include<vector>#include<map>#include<queue>#include& 查看详情

hdu2473junk-mailfilter(并查集的删除操作)

题目地址：pid=2473">HDU2473这题曾经碰到过，没做出来。。如今又做了做，还是没做出来。。、、这题涉及到并查集的删除操作。想到了设一个虚节点，可是我把虚节点设为了要删除的点的父节点。一直是栈溢出，目測是无限递归... 查看详情

hdu2473junk-mailfilter并查集删点，模板题(代码片段)

TimeLimit:15000/8000MS(Java/Others)    MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):10376    AcceptedSubmission(s):3280ProblemDescriptionRecognizingj 查看详情

hdu2473junk-mailfilter并查集，虚拟删除操作

给定两种操作第一种是合并XY第二种是把X分离出来，就是从原来的集合中分离出来，其它的关系不变。 关键是怎么分离，可以考虑把它变成一个其它值。HASH[i]=other_val然后用新值去做并查集即可、需要注意的一点就是加入现... 查看详情

hdu2473junk-mailfilter(并查集设辅助点)(代码片段)

题目链接题目大意??有n个编号为0~n的物品，并且有两个操作，分别是将两个物品合并在一个集合里和把一个物品从集合里取出来，问最后有多少个集合。解题思路??本题主要是如何把物品从集合中取出，可以设立一个与原物品编... 查看详情

hdu2473（并查集删除点）

...删除a点，所有的操作结束后输出集合的个数。题解：用并查集。删除集合中的点，建立虚父节点。删除操作：合并操作就是找到找到两个节点的父亲，修改父亲，如果删除就是将该点的父亲重新设置成自己，但是这是不行的，... 查看详情

hdu2473(代码片段)

hdu2473并查集的删除操作建立虚点，删除它就断掉了它在原图中的所有关系，而成为独立节点，而且它只能被删除一次，而且删除之后还能进行操作，采用映射（虚点）的方法，建立虚点并把删除之后的操作挪到虚点上来。啊，... 查看详情

并查集的删除操作(代码片段)

...一开始所有信件都是单独的文件夹。其实就是一个简单的并查集删除的操作，当删除时就创建新的结点来代替它,要注意的是数组的范围，虽然信件只有10的5次方，但是操作有10的6次方，因为删除时还得 查看详情

hdu5652indiaandchinaorigins并查集

IndiaandChinaOrigins ProblemDescriptionAlongtimeagotherearenohimalayasbetweenIndiaandChina,thebothculturesarefrequentlyexchangedandarekeptinsyncatthattime,buteventuallyhimalayasriseup.Withthatatf 查看详情

hdu3938并查集

求小于L的路径点对数（路上的最大值），按权值排序，从小到大并查集建图，有点kruskal的意思。/**@Date:2017-09-2217:30:11*@FileName:HDU3938并查集离线.cpp*@Platform:Windows*@Author:Lweleth([email protected])*@Link:https://github.com/*@Version:$Id$ 查看详情

hdu1856并查集

http://acm.hdu.edu.cn/showproblem.php?pid=1856  MoreisbetterTimeLimit:5000/1000MS(Java/Others)    MemoryLimit:327680/102400K(Java/Others)TotalSubmission(s):29843 &nb 查看详情

hdu1325并查集

http://acm.hdu.edu.cn/showproblem.php?pid=1325 IsItATree?TimeLimit:2000/1000MS(Java/Others)    MemoryLimit:65536/32768K(Java/Others)TotalSubmission(s):26387   & 查看详情

hdu1213howmanytables（并查集）

传送门DescriptionTodayisIgnatius‘birthday.Heinvitesalotoffriends.Nowit‘sdinnertime.Ignatiuswantstoknowhowmanytablesheneedsatleast.Youhavetonoticethatnotallthefriendsknoweachother,andallthefriendsdonotwan 查看详情

hdu4496并查集

http://acm.hdu.edu.cn/showproblem.php?pid=4496 D-CityTimeLimit:2000/1000MS(Java/Others)    MemoryLimit:65535/65535K(Java/Others)TotalSubmission(s):4802     查看详情

*hdu3172并查集

VirtualFriendsTimeLimit:4000/2000MS(Java/Others)    MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):8165    AcceptedSubmission(s):2345ProblemDescription 查看详情

hdu1213howmanytables（模板——并查集）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1213ProblemDescriptionTodayisIgnatius‘birthday.Heinvitesalotoffriends.Nowit‘sdinnertime.Ignatiuswantstoknowhowmanytablesheneedsatleast.Youhavetonoticetha 查看详情

*hdu1829并查集

ABug‘sLifeTimeLimit:15000/5000MS(Java/Others)    MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):14121    AcceptedSubmission(s):4603ProblemDescriptionBa 查看详情

*hdu3047并查集

ZjnuStadiumTimeLimit:2000/1000MS(Java/Others)    MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):3062    AcceptedSubmission(s):1182ProblemDescriptionIn1 查看详情