题解 2018寒假训练1 H.垃圾邮件过滤器(虚拟结点)
zhouwc
2018-02-25 09:45:45
问题 H: 垃圾邮件过滤器
时间限制: 1 Sec 内存限制: 128 MB
[提交][状态][讨论版]
题目描述
要处理垃圾邮件，就要对邮件归类。现在有n封邮件，邮件编号0~n-1，m个操作：
1. M X Y 表示邮件X和Y是同一类
2. S X 表示邮件X是特殊类，这个时候，他就要独立出来单独归类
比如有3封邮件，3个操作： M 0 1， M 1 2， S 1
前两个操作表示0 1 2封邮件都属于一类，经过第三个操作后，发现1是特殊类，但0 2还是属于同一类，于是总共有两类邮件。
现在问题就是给你这些邮件和操作，问总共有几类邮件？
输入
输入n m
输入m个操作，如描述格式
输出
输出有几类邮件
样例输入
3 3
M 0 1
M 1 2
S 1
样例输出
2
提示
【样例说明】
其他样例：
输入：
5 6
M 0 1
M 1 2
M 1 3
S 1
M 1 2
S 3
输出：
3
解释：
前三个操作把0 1 2 3归为一类，
然后发现1要单独归类，于是把1与0 2 3分开
后来发现1和 2是同一类，于是继续把1归到2的分类中
最后发现3是单独一类
最终0 1 2是一类，3一类，4一类
总共3类
【数据规模和约定】
1<=N<=10^5
1<=M<=10^6
题解
没出现两个结点合并，出现1个结点删除其原来的关系，但原来的关系网不会因为它而改变
比如M 0 1, M 1 2, S 1,删除了1，原来因为1才分为一类的0 2还是归为一类
所以问题需要本来连接0 2的1还存在，这里就引进虚结点
0-1-2，如果要删除1，改成将1从新定位到新结点(从n开始编号)，变为
0-1(虚拟)-2 3(为原来的1)
这样的话，还是分为了2类，第一类0 1 2，只不过1是虚拟结点，第二类是3，这个3本来是1
所以对于每个结点，设一个id[i]，表示它将映射成新结点
初始的时候,id[i]=i, 需要改变的时候id[i]=tot++;
剩下的做法，还是基本的并查集。
```cpp
#include<cstdio>
#include<cstring>
using namespace std;
int fg[110005],fa[110005],id[1100005];
int n,m,a,b,tot,root,ans;
char c;
int find(int x){
if(fa[x]!=x) fa[x]=find(fa[x]);
return fa[x];
}
int main(){
scanf("%d%d",&n,&m);
tot=n;
for(int i=0;i<n+m;i++){
fa[i]=i;
id[i]=i;
}
for(int i=0;i<m;i++)
{
scanf(" %c",&c);
if(c=='S')
{
scanf("%d",&a);
id[a]=tot++;
}else
{
scanf("%d%d",&a,&b);
fa[find(id[b])]=find(id[a]);
}
}
for(int i=0;i<n;i++)
fg[find(id[i])]=1;
for(int i=0;i<tot;i++)
{
if(fg[i])ans++;
}
printf("%d",ans);
return 0;
}
```