題干：

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, so?
relationships (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 6 M 0 1 M 1 2 M 1 3 S 1 M 1 2 S 33 1 M 1 20 0

Sample Output

Case #1: 3 Case #2: 2

解題報告：

? ? ? ? 并查集刪點問題，虛擬一個節(jié)點，f數(shù)組開到n+m，用來找real點的父節(jié)點，real開到n，用來存輸入數(shù)據(jù)的真實值（輸入的也都是小于n的，但是real數(shù)組可以將其映射到>n上，換句話說，real的下標一定小于n（此題取不到等號），但是real的內容可以大于n，其實也就是 可能是那個從n+1開始的id值）。注意一些細節(jié)以及背過這一個模板即可。

ac代碼：

#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> const int MAXn = 1e5 + 5;//點數(shù) const int MAXm = 1e6 + 5;//指令數(shù) using namespace std; int n,m; int cnt,id; char op[5]; int f[MAXn+MAXm+5]; int real[MAXn+5];//real不需要開到MAXm！！ int bk[MAXn+MAXm+5]; int getf(int v) {if(f[v]!=v)f[v]=getf(f[v]);return f[v]; } void init() {cnt=0;id=n+1;for(int i = 1; i<=n; i++) {real[i]=i;f[i]=i;}memset(bk,0,sizeof(bk) ); }void merge(int u,int v) {int t1=getf(u);int t2=getf(v);if(t1!=t2) f[t2]=t1; } void del(int u) {real[u]=id;f[id]=id;//必須要有，因為f數(shù)組只賦值到n，所以要賦值！ id++; }int main() {int u,v;int iCase=0;while(~scanf("%d %d",&n,&m) ) {if(m==0 && n==0) break;init();while(m--) {scanf("%s",op);if(op[0]=='M') {scanf("%d %d",&u,&v);merge(real[u],real[v]);}else {scanf("%d",&u);del(u);//？有疑問？ //必須u！！不能real[u]！ 想想也知道啊因為del里面real[i]其中i要<n的（因為開的數(shù)組real[]開到了n，就是 記錄輸入的點的真實值，而輸入的點最大是n）！所以你傳的i肯定要<n啊所以不能是real[u]！ } //其實如果 傳real[u]，你想找到他就需要real[real[u]]了！顯然不符合了。。整個結構都改變了，因為你可能兩層real嵌套就可能三層四層、、代碼沒法實現(xiàn)了就。 }for(int i = 0; i<n; i++) {//此題規(guī)定了！從 0 開始！ if(bk[getf(real[i] ) ] ==0) {//別忘加getf！！ bk[getf(real[i] ) ]=1;cnt++;}} printf("Case #%d: %d\n",++iCase,cnt);}return 0 ; }

ac代碼2：（可以再看看？）

分析：這道題是一道典型的并查集的題目，關鍵是節(jié)點從集合中刪除的s操作
這里使用了節(jié)點數(shù)的的下標+n作為父節(jié)點，這個位置只是標記父節(jié)點，并沒其他含義，等于是虛擬的節(jié)點。
這樣當刪除一個節(jié)點時只用從這個節(jié)點中拿出來讓其父節(jié)點重新放在一個虛擬的位置，即下標從n+n開始向后找。
最后是查找獨立特點的集合。將這些父節(jié)點放在一個長度為n的num的數(shù)組中，里邊放置的每個節(jié)點對應的父節(jié)點的位置，
然后對這個數(shù)組排序，找出其中不同父節(jié)點的數(shù)目即集合的個數(shù)。

#include <iostream> #include <stdio.h> #include <algorithm> #define MAXNUM1 100005 #define MAXNUM2 1000005using namespace std; int f[MAXNUM1*2+MAXNUM2],num[MAXNUM1];int getf(int a) {if(f[a]==a)return a;else return f[a]=getf(f[a]); } int main() {int n,m,ca,x,y,total;char op[3];ca = 0;while(scanf("%d%d",&n,&m)!=EOF&&n){for(int i=0;i<n;i++)f[i]=i+n;for(int i=n;i<=n+n+m;i++)f[i]=i;total = n+n;for(int t=0;t<m;t++){scanf("%s",op);if(op[0]=='M'){scanf("%d%d",&x,&y);int rx = getf(x);int ry = getf(y);if(rx!=ry) f[rx]=ry;}else{scanf("%d",&x);f[x] = total++;}}for(int i = 0; i < n; i++)num[i] = getf(i);sort(num,num+n);int ans=1;for(int i = 1; i < n;i++)if(num[i]!=num[i-1])ans++;printf("Case #%d: %d\n",++ca,ans);}return 0; }

?

?

?

?

總結：

? ? ? 1.初始化的時候啊 ?i<n寫成i<m了，，粗心？

? ? ? 2.看清題目啊本題要求了從0開始的點，你最后遍歷的時候還從1開始，，，讀題？

? ? ? 3.其他要注意的點都寫在代碼里了，值得注意的就是加深一下對f數(shù)組和real數(shù)組的理解！

總結

以上是生活随笔為你收集整理的*【HDU - 2473】Junk-Mail Filter （并查集--删点操作）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。