本文主要是介绍hdu 2473 Junk-Mail Filter 并查集 删除点，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：有n封邮件现在要将其含有相同的特征的放在一起，
M X Y代表X，Y具有相同的特征，S Y代表Y被错判了
现在问你这两种操作完成后还有多少种的信，注意
特征可以传递 X Y 有相同特征Y Z有相同的特征，则
X Y Z同时具有相同的特征。如果X Y Z中有一个被
误判这剩下的两个仍然具有相同的特征。
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
int set[1000001],rank[1000001],v1[1000001];
int find(int x)
{if(set[x]!=x){set[x]=find(set[x]);}return set[x];
}
void get(int x,int y)
{int xx=find(x);int yy=find(y);if(xx!=yy){set[xx]=yy;rank[yy]+=rank[xx];rank[xx]=0;}
}
int main()
{int n,m;char ch;int u,v;int Case=1;while(~scanf("%d %d",&n,&m),n||m){int num=n;int s=0;for(int i=0; i<n; i++){set[i]=i;v1[i]=i;rank[i]=1;}while(m--){getchar();scanf("%c",&ch);if(ch=='M'){scanf("%d %d",&u,&v);get(v1[u],v1[v]);}else{scanf("%d",&u);int xx=find(v1[u]);rank[xx]--;rank[num]=1;v1[u]=num;set[num]=num++;}}for(int i=0; i<num; i++)if(rank[i]>0)s++;printf("Case #%d: %d\n",Case++,s);}return 0;
}第一次接触并查集删除的题目看了别人的代码才懂得
因为并查集是树形结构，所以无法简单的把一个节点从一棵树中删去并维护原来的信息。那这里用到的思想就是还是保持原来的树的结构不变，只是把被删掉的那个点设为虚点，并新建一个点，把原来的点映射到这个新点上，代表以后的操作都是对这个新点进行操作。这样空间开销虽然大，但还是可以解决问题的。
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int rank[20000],v[22000],set[20000];
int find(int x)
{int y=set[x];if(set[x]!=x){set[x]=find(set[x]);rank[x]+=rank[y];}return set[x];
}
void get(int x,int y)
{int xx=find(x);int yy=find(y);if(xx!=yy){set[xx]=yy;rank[yy]+=rank[yy];rank[xx]=0;}
}
int main()
{int n,m;char ch;int a,b;int Case=1,s;while(~scanf("%d %d",&n,&m),n||m){int num=n;s=0;for(int i=0; i<=n; i++){set[i]=i;v[i]=i;rank[i]=1;}while(m--){getchar();scanf("%c",&ch);if(ch=='M'){scanf("%d %d",&a,&b);get(v[a],v[b]);}else{scanf("%d",&a);int xx=find(v[a]);rank[v[a]]=0;rank[xx]--;rank[num]=1;v[a]=num;set[num]=num++;}}for(int i=0; i<num; i++)if(rank[i]>0)s++;printf("Case #%d: %d\n",Case++,s);}
}
这篇关于hdu 2473 Junk-Mail Filter 并查集 删除点的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
