Description
Recognizing junk mails is a tough task. The method used here consists of two steps:1) Extract the common characteristics from the incoming email. 2) Use a filter matching the set of common characteristics extracted to determine whether the email is a spam.We want to extract the set of common characteristics from the N sample junk emails available at the moment, and thus having a handy data-analyzing tool would be helpful. The tool should support the following kinds of operations:a) “M X Y”, meaning that we think that the characteristics of spam X and Y are the same. Note that the relationship defined here is transitive, sorelationships (other than the one between X and Y) need to be created if they are not present at the moment.b) “S X”, meaning that we think spam X had been misidentified. Your tool should remove all relationships that spam X has when this command is received; after that, spam X will become an isolated node in the relationship graph.Initially no relationships exist between any pair of the junk emails, so the number of distinct characteristics at that time is N.Please help us keep track of any necessary information to solve our problem.
Input
There are multiple test cases in the input file. Each test case starts with two integers, N and M (1 ≤ N ≤ 10 5 , 1 ≤ M ≤ 106), the number of email samples and the number of operations. M lines follow, each line is one of the two formats described above.Two successive test cases are separated by a blank line. A case with N = 0 and M = 0 indicates the end of the input file, and should not be processed by your program.
Output
For each test case, please print a single integer, the number of distinct common characteristics, to the console. Follow the format as indicated in the sample below.
Sample Input
5 6M 0 1M 1 2M 1 3S 1M 1 2S 33 1M 1 20 0
Sample Output
Case #1: 3Case #2: 2
FA
/*题意：有n个邮件，编号为0~n-1，有两种操作1、M x y 将x和y合并成为一类邮件2、S x 将x从所属邮件集合中取出求有多少各不同集合思路：设立虚父结点，一般并查集初始化的时候每个点的父结点都是自己，本题要删结点，一般并查集的初始化方法行不通，举个例子，比如1,2,3的父结点都是1，现在删除1，1的父结点还是1，2,3的父结点也为1，集合数还是1，正确答案为2我们为每一个结点设立一个虚父结点，即初始化的时候不再将每个结点的父结点设置为自己本身。比如1,2,3初始化时，可以将他们的父结点设置为4,5,6假如1,2,3还是一个集合，他们的父结点都为4，删除结点1，那么1的父结点为7，，2,3的父结点还是4*/#include <iostream>#include <queue>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#include <cstdlib>#include <string>#include <map>using namespace std;const int N = 2000010;int bin[N];//注意数组的大小bool vis[N];void init(int &n,int &m){for(int i = 0; i < n; i ++)bin[i] = i+n;//每个结点的父亲不再是自己for(int i = n; i <= (n<<1)+m; i ++)//因为有m次操作，所以要多初始化m个bin[i] = i;//虚父结点的父亲是自己本身}int Find(int x){return bin[x]==x? x : bin[x] = Find(bin[x]);}void Merge(int x, int y){int fx = Find(x);int fy = Find(y);if(fx!=fy)bin[fx] = fx;}int main(){int n,m,x,y,i,j,p=1;char s[5];while(scanf("%d%d",&n,&m),(n+m)){init(n,m);int cnt = 2*n;//cnt表示删除结点时，cnt作为新结点的虚父结点，要从2*n开始while(m–){scanf("%s",s);if(s[0] == 'M'){scanf("%d%d",&x,&y);Merge(x,y);}if(s[0] == 'S'){scanf("%d",&x);bin[x] = cnt++;//为删除的结点设置一个虚父结点}}memset(vis, false, sizeof(vis));int ans = 0;for(i = 0; i < n; i ++){if(!vis[Find(i)]){vis[Find(i)] = true;ans ++;}}printf("Case #%d: %d\n",p++,ans);}return 0;}#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]==x?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(d[a],d[b]);}else{scanf("%d",&a); //a有两个指向,bin[x](众多集合的根),d[x](孤立结点的根);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("Case #%d: %d\n",num,sum);}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
大多数人想要改造这个世界，但却罕有人想改造自己。
