首页 > 代码库 > HDU 2473 Junk-Mail Filter(并查集的删除操作)
HDU 2473 Junk-Mail Filter(并查集的删除操作)
题目地址:HDU 2473
这题以前碰到过,没做出来。。现在又做了做,还是没做出来。。、、
这题涉及到并查集的删除操作。想到了设一个虚节点,但是我把虚节点设为了要删除的点的父节点,一直是栈溢出,目测是无限递归了。看了看别人的做法, 原来只要建一个映射就可以了,虚节点是作为的新的映射,每次删除一个点,就把他映射到一个新的点上去。
代码如下:
#include <iostream> #include <cstdio> #include <string> #include <cstring> #include <stdlib.h> #include <math.h> #include <ctype.h> #include <queue> #include <map> #include <set> #include <algorithm> using namespace std; int bin[2100000], _hash[2100000], d[2100000]; int find1(int x) { return bin[x]==d[x]?d[x]:bin[x]=find1(bin[x]); } void join(int x, int y) { int f1=find1(x); int f2=find1(y); if(f1!=f2) bin[f2]=f1; } int main() { int n, m, i, cnt, num=0, sum, a, b; char c; while(scanf("%d%d",&n,&m)!=EOF&&n+m) { num++; sum=0; cnt=n; for(i=0; i<2000000; i++) { bin[i]=i; d[i]=i; } while(m--) { getchar(); scanf("%c",&c); if(c=='M') { scanf("%d%d",&a,&b); join(a,b); } else { scanf("%d",&a); bin[a]=cnt; d[a]=cnt++; } } memset(_hash,0,sizeof(_hash)); for(i=0; i<n; i++) { a=find1(d[i]); if(!_hash[a]) { sum++; _hash[a]=1; } //printf("%d ",a); } //puts(""); printf("Case #%d: %d\n",num,sum); } return 0; }
HDU 2473 Junk-Mail Filter(并查集的删除操作)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。