首页 > 代码库 > hdu 2473 Junk-Mail Filter 并查集删除
hdu 2473 Junk-Mail Filter 并查集删除
点击打开链接 http://acm.hdu.edu.cn/showproblem.php?pid=2473
题意:给出n种操作,M a b表示a和b是同一个并查集,S a表示在并查集中删除a,要注意的是,如果1和2是一个并查集,2和3是一个并查集,那么1和3也是一个并查集,即使删除2之后,我们依然可以得到1和3还是一个集合里的。
思路:由于并查集是一种树结构,无法在树种删除一个点后还让树继续保持着之前的样子,所以我们删除是采取的操作是使用映射,一开始所有点的映射都是自己,然后删除操作就是把这个点映射到另一个不存在的点上,这样原来的点还在原来的集合中,用来保持着原先集合的各种属性,之后的所有对这个点的操作都是对它映射的点的操作。与一般的并查集不同的是,找父亲的操作,找的不是这个点本身的父亲,而是所有点的映射的父亲。
<pre name="code" class="cpp">#include<cstdio> #include<cstring> #include<iostream> using namespace std; const int maxn=2000100; int f[maxn],id[maxn]; bool a[maxn]; int fin(int x){ if(x==f[x]) return x; f[x]=fin(f[x]); return f[x]; } int main() { int cas=1; int n,m; while(cin>>n>>m){ if(!n&&!m) break; for(int i=0;i<maxn;i++){ f[i]=i; id[i]=i; a[i]=0; } char s; int b,c; int num=n; for(int i=0;i<m;i++){ getchar(); scanf("%c",&s); if(s=='M'){ scanf("%d %d",&b,&c); int fb=fin(id[b]); int fc=fin(id[c]); if(fb!=fc) f[fb]=fc; } else{ scanf("%d",&b); id[b]=num++; } } int ans=0; for(int i=0;i<n;i++) if(a[fin(id[i])]==0){ ans++; a[fin(id[i])]=1; } printf("Case #%d: %d\n",cas++,ans); } return 0; }
hdu 2473 Junk-Mail Filter 并查集删除
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。