题目大意：有n封邮件现在要将其含有相同的特征的放在一起，M X
Y代表X，Y具有相同的特征，S Y代表Y被错判了现在问你这两种操作完成后还有多少种的信，注意特征可以传递 X Y 有相同特征Y Z有相同的特征，则X Y
Z同时具有相同的特征。如果X Y
Z中有一个被误判这剩下的两个仍然具有相同的特征。需要注意的是当1和2并上，2和3并上，2被删除后，1与3是依然并在一起的。
题解：设立虚拟根节点，1~n为固定根节点,n+1~n+n作为根节点作为前者的父节点，之后再增添n+n~n+n+m作为备用节点，删除时直接修改1~n指向的节点到n+n后的节点，这样就不会影响其它节点的信息了。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32 |
#include <cstdio> #include <iostream>using
namespace std;int T=1,n,m,x,y,cnt,f[2000500],flag[4000500],ans;char
c;int sf(int
x){return
x==f[x]?x:f[x]=sf(f[x]);}void
Union(int
x,int y){f[sf(x)]=sf(y);}int scan(int
&x){ while(c=getchar(),c<‘0‘||c>‘9‘);x=c-‘0‘; while(c=getchar(),c>=‘0‘&&c<=‘9‘)x=x*10+c-‘0‘;}int
main(){ while(scanf("%d%d",&n,&m),n||m){ cnt=n*2,ans=0; for(int
i=0;i<n;i++)f[i]=i+n; for(int
i=n;i<n*2+m;i++)f[i]=i; memset(flag,0,sizeof(flag)); for(int
l=0;l<m;l++){ scanf(" %c",&c); if(c==‘M‘){ scan(x);scan(y); Union(x,y); }else{ scan(x); f[x]=cnt++; } } for(int
i=0;i<n;i++){if(flag[sf(i)]==0){ans++,flag[sf(i)]=1;}} printf("Case #%d: %d\n",T++,ans); } return
0; } |
原文：http://www.cnblogs.com/forever97/p/3551742.html