C - Junk-Mail Filter HDU - 2473
2020补充：发现当初写得不清不楚，重新补充一下。
并查集的删除操作是采用的是一个映射操作。
如上图，在原并查集的基础上，我们加多一个映射数组。当我们要把1从（1,2）集合中删除，实际上便是多创建一个3，然后把1映射到3上，之后所有对1的操作其实便是对3的操作。
所以删除操作便是，创建一个新的元素，让要删除的元素映射新的元素，之后所有对删除的元素的操作，都是对它映射的元素的操作。
题目大意：就是一堆信件，然后有两个操作，一个是把一堆信件归在一个文件夹，一个就是把一个信件从文件夹中取出，最后问有多少个文件夹，一开始所有信件都是单独的文件夹。
其实就是一个简单的并查集删除的操作，当删除时就创建新的结点来代替它,要注意的是数组的范围，虽然信件只有10的5次方，但是操作有10的6次方，因为删除时还得创建新节点，所以数组一定要开大，不然不是WR就是TL。最后的输出可以直接用set，也可以用数组标记信件是归在哪个文件夹，注意的是后面创建的结点是虚拟的，真实的信件有对它们的映射，所以最后统计时只考虑真实信件。
1 #include<cstdio> 2 #include<iostream> 3 #include<set> 4 using namespace std; 5 struct Email{ 6 int id,gen; 7 }em[1201108];//要够大 8 int n,m; 9 int gui(int x); 10 void bing(int x,int y); 11 void del(int x); 12 int main() 13 { 14 int i,x,y,test=0; 15 char c; 16 while(scanf("%d%d",&n,&m)!=EOF&&(n||m)) 17 { 18 int N=n; 19 set<int> s; 20 for(i=0;i<n;i++) 21 { 22 em[i].id=i; 23 em[i].gen=i; 24 }//初始自己映射自己，自己是自己的根节点。。。。 25 while(m--) 26 { 27 cin>>c; 28 if(c=='M') 29 { 30 scanf("%d%d",&x,&y); 31 bing(em[x].id,em[y].id); 32 } 33 else 34 { 35 scanf("%d",&x); 36 del(x); 37 } 38 } 39 for(i=0;i<N;i++)//只考虑真实信件 40 s.insert(gui(em[i].id));//每个集合的根节点只记录一次 41 printf("Case #%d: %d ",++test,s.size()); 42 } 43 return 0; 44 } 45 int gui(int x) 46 { 47 if(em[x].gen==x) 48 return x; 49 return em[x].gen=gui(em[x].gen); 50 } 51 void bing(int x,int y)//对节点所映射的节点进行并操作 52 { 53 int bx=gui(x); 54 int by=gui(y); 55 if(bx!=by) 56 em[by].gen=bx; 57 return ; 58 } 59 void del(int x)//创造虚拟节点来代替原来节点 60 { 61 em[x].id=n;//节点映射到新创建的虚拟节点 62 em[n].gen=n; 63 n++; 64 return ; 65 }