题解：SP5150 JMFILTER - Junk-Mail Filter

md 什么输出格式，什么输出格式，什么输出格式，什么输出格式，什么输出格式，什么输出格式，什么输出格式，调了我一个小时。（请不要理会这位疯子）

样例解释

首先实现肯定是并查集，但是要支持删除一个点。

这是样例的图。

图丑勿喷（。

样例先给 $1$ 删掉，变成了这样。

然后连 $1$ 和 $2$，删掉 $3$。

有 $3$ 个连通块，输出 $3$。

思路

对于删除操作我们可以造假点，就像这样。

每一个真点 $i$ 都向假点 $i+n$ 连一条边。

当我们要删除 $1$ 号节点就将 $1$ 号节点的假点改成其他数就行了。

要删除点时，就将她所对应的假点改变就行。

对于空间，原本有 $n\times2$ 个点，删点还要新增点，最多 $2n+m$ 个点。

最后注意一下输出格式就行了。

#include<bits/stdc++.h>
using namespace std;
int n,m,fa[2145140],cnt;
set<int> ans;
int find(int x){
	if(fa[x]==x)return x;
	return fa[x]=find(fa[x]);
}
void hb(int x,int y){
	x=find(x),y=find(y);
	if(x!=y)fa[x]=y;
}
void del(int x){
	fa[x]=cnt++;
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int t=0;
	while(cin>>n>>m){
		if(!n&&!m)return 0;
		for(int i=0;i<n;i++)fa[i]=i+n;//向虚点 i+n 连一条边 
		cnt=n*2;
		for(int i=n;i<=cnt+m;i++)fa[i]=i;//虚点的父亲是自己 
		for(int i=1;i<=m;i++){
			char op;int x,y;
			cin>>op>>x;
			if(op=='M')cin>>y,hb(x,y);
			else del(x);
		}
		ans.clear();
		for(int i=0;i<n;i++)ans.insert(find(i));
		cout<<"Case #"<<++t<<": "<<ans.size()<<"\n";
	}
	return 0;
}