题解 SP5150 【JMFILTER - Junk-Mail Filter】

· · 题解

并查集删点模板题

合并方法与普通并查集一样

删点方法：造假点；

因为我们不知道要删除的点是根节点还是叶节点，所以如果直接删除（用其他点替换）可能会影响到其他节点，于是我们得到了做法：

全部修改，让构造的时候就没有使用真点，及一直用假点来代替，删点的时候只需更改原来的点指向的假点即可，即为造假点。

思路有两种：

  1. 在父节点数组中设0~n-1为原来的点，n~2*n-1为假点，2*n~2*n+m为删点时用的，即备用假点（这种方法我一直没改对，不放代码了）

  2. 开两个数组，一个是原来的点，一个是用来标记点对应假点。

至于怎么判断有多少个集合：

扫一遍所以点，找到每一个点的祖宗，如果没有被找到，答案加一并标记，否则不做处理（即找有多少种祖宗）。

PS：大数据请使用较快的读入方式。

发现好多大佬放到标程都没有注释哎，我太菜，只好写点注释（完美的逻辑。。。）。

代码：

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int f[1000010],id[1000010],n,m,x,y,ans,cnt,ji;//f是父节点，id是对应的假点，数组开大一点（
char a[3];
bool b[1000010];
int find(int x)
{
    if(f[x]==x)
    return x;
    return f[x]=find(f[x]);
}//寻找祖宗+压缩路径
int read()        
{        
    int s = 0, f = 1;        
    char ch = getchar();        
    while(!isdigit(ch)) {        
        if(ch == '-') f = -1;        
        ch = getchar();        
    }        
    while(isdigit(ch)) {        
        s = s * 10 + ch - '0';        
        ch = getchar();        
    }        
    return s * f;        
}
int main()
{
    while(n=read(),m=read(),n|m)
    {
        cnt=n;
        for(int i=1;i<=n;i++)
        f[i]=id[i]=i;//初始化
        for(int i=1;i<=m;i++)
        {
            scanf("%s",a+1);
            if(a[1]=='M')
            {
                int x=read()+1,y=read()+1;//把数组向后移，变成1~n，便于思考
                int fx=find(id[x]),fy=find(id[y]);//找到对应假点的祖宗
                if(fx!=fy)
                f[fy]=fx;//合并
            }
            else 
            {
                int x=read()+1;
                id[x]=++cnt;//把对应点的指针指向一个新的点（相当于删除了）
                f[id[x]]=id[x];//初始化新点的父节点指针
            }
        }
        memset(b,0,sizeof(b));//重置记录答案的部分
        ans=0;
        for(int i=1;i<=n;i++)
        {
            int qwq=find(id[i]);
            if(!b[qwq])//统计答案
            {
                ans++;
                b[qwq]=1;
            }
        }
    printf("Case #%d: %d\n",++ji,ans);
    }
    return 0;
}