正文

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

llguanli  llguanli  2022-09-05  491

关键词：

Problem Description

Recognizing junk mails is a tough task. The method used here consists of two steps:
1) Extract the common characteristics from the incoming email.
2) Use a filter matching the set of common characteristics extracted to determine whether the email is a spam.

We want to extract the set of common characteristics from the N sample junk emails available at the moment, and thus having a handy data-analyzing tool would be helpful. The tool should support the following kinds of operations:

a) “M X Y”, meaning that we think that the characteristics of spam X and Y are the same. Note that the relationship defined here is transitive, so
relationships (other than the one between X and Y) need to be created if they are not present at the moment.

b) “S X”, meaning that we think spam X had been misidentified. Your tool should remove all relationships that spam X has when this command is received; after that, spam X will become an isolated node in the relationship graph.

Initially no relationships exist between any pair of the junk emails, so the number of distinct characteristics at that time is N.
Please help us keep track of any necessary information to solve our problem.

Input

There are multiple test cases in the input file.
Each test case starts with two integers, N and M (1 ≤ N ≤ 10⁵ , 1 ≤ M ≤ 10⁶), the number of email samples and the number of operations. M lines follow, each line is one of the two formats described above.
Two successive test cases are separated by a blank line. A case with N = 0 and M = 0 indicates the end of the input file, and should not be processed by your program.

Output

For each test case, please print a single integer, the number of distinct common characteristics, to the console. Follow the format as indicated in the sample below.

Sample Input

Sample Output

Case #1: 3
Case #2: 2

题意：S是将该点从集合中剥离出来，M是联合起来。求出最后的联通块
思路：就是并查集的删除操作了！多开一个数组来记录当前点的映射位置！由于眼下还没有其它的算法能将并查集的节点分离出来而不影响其结构。所以分离出来的点的映射位置应为之前没出现的点，合并操作的时候也是要这样操作映射数组！
所以AC代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<set>
using namespace std;

const int maxn=100000+10;
int f[maxn*10],a[maxn];

int find(int x)
{
    if(x!=f[x])
        f[x]=find(f[x]);
    return f[x];
}

void Union(int x,int y)
{
    x=find(x);
    y=find(y);
    if(x==y)return ;
    f[x]=y;
}

set<int>s;

int main()
{
    #ifndef ONLINE_JUDGE
    freopen("in.cpp","r",stdin);
    freopen("out.cpp","w",stdout);
    #endif // ONLINE_JUDGE
    int n,m;
    char str[2];
    int cas=1;
    while(scanf("%d %d",&n,&m)==2&&(n+m))
    {
        s.clear();
        for(int i=0;i<=n;i++)
        {
            f[i]=i;
            a[i]=i;
        }
        int num=n;
        while(m--)
        {
            scanf("%s",str);
            if(str[0]==‘S‘)
            {
                int k;
                scanf("%d",&k);
                a[k]=num++;
                f[a[k]]=a[k];
            }
            else
            {
                int x,y;
                scanf("%d %d",&x,&y);
                Union(a[x],a[y]);
            }
        }

        for(int i=0;i<n;i++)
        {
            s.insert(find(a[i]));
        }
        printf("Case #%d: %d
",cas++,s.size());
    }
    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 查看详情