合纵连横
时间限制：1000 ms | 内存限制：65535 KB
难度：3
描述
乱世天下，诸侯割据。每个诸侯王都有一片自己的领土。但是不是所有的诸侯王都是安分守己的，实力强大的诸侯国会设法吞并那些实力弱的，让自己的领土面积不断扩大。而实力弱的诸侯王为了不让自己的领土被吞并，他会联合一些其他同样弱小的诸侯国，组成联盟(联盟不止一个)，来共同抵抗那些强大的诸侯国。 强大的诸侯国为了瓦解这些联盟，派出了最优秀的间谍来离间他们，使一些诸侯国退出联盟。最开始，每个诸侯国是一个联盟。
有两种操作
1、U x y 表示x和y在同一个联盟。（0≤x，y
#include<bits/stdc++.h>
using namespace std;const int MAXN = 1e5*3;
const int MAXM = 1e6 ;int pre[MAXN],pos[MAXN],num[MAXN],tot,sz;
void Init(int n){ // 初始化for(int i=0;i<=n;i++){pos[i]=pre[i]=i;num[i]=1;}tot=n; sz=n;
}
int Find(int x){ // 查return x==pre[x]?x:(pre[x]=Find(pre[x]));
}
bool Join(int x,int y){ // 并 x并到上y，这里要注意传进参数的顺序x=pos[x]; y=pos[y];int fx=Find(x); int fy=Find(y);if(fx==fy) return false;pre[fx]=fy;num[fy]+=num[fx];sz--;return true;
}
bool Del(int x){
//删int fx=Find(pos[x]);if(num[fx]==1) return false;num[fx]--;pos[x]=++tot;pre[tot]=tot;num[tot]=1;sz++;return true;
}int main(){int n,m; int ncase=1;while(scanf("%d%d",&n,&m)!=EOF){Init(n); char op[10];while(m--){scanf("%s",op);if(op[0]=='U'){int a,b;scanf("%d%d",&a,&b); a++;b++;Join(a,b);}else {int x; scanf("%d",&x); x++;Del(x);}}printf("Case #%d: %d\n",ncase++,sz);}return 0;
}