合纵连横
时间限制：1000 ms | 内存限制：65535 KB
难度：3
- 描述
-
乱世天下，诸侯割据。每个诸侯王都有一片自己的领土。但是不是所有的诸侯王都是安分守己的，实力强大的诸侯国会设法吞并那些实力弱的，让自己的领土面积不断扩大。而实力弱的诸侯王为了不让自己的领土被吞并，他会联合一些其他同样弱小的诸侯国，组成联盟(联盟不止一个)，来共同抵抗那些强大的诸侯国。 强大的诸侯国为了瓦解这些联盟，派出了最优秀的间谍来离间他们，使一些诸侯国退出联盟。最开始，每个诸侯国是一个联盟。
有两种操作
1、U x y 表示x和y在同一个联盟。（0≤x，y<n）
2、D x 表示x退出联盟。
- 输入
- 多组测试数据
第一行两个数，n和m（1 ≤ n≤ 10^5, 1 ≤ m ≤10^5），分别表示诸侯国的个数和操作次数。
接下来有m行操作 - 输出
- 输出联盟的个数
- 样例输入
-
5 7 U 0 1 U 1 2 U 0 3 D 0 U 1 4 D 2 U 0 2 10 1 U 0 9
- 样例输出
-
Case #1: 2 Case #2: 9
#include<stdio.h> #include<string.h> #define MAX 1001000 int set[MAX],vis[MAX]; int mark[MAX]; int n,m,count; void init() { int i,j; for(i=0;i<n;i++) { set[i]=i; vis[i]=i; } } int find(int fa) { int t; int ch=fa; while(fa!=set[fa]) fa=set[fa]; while(ch!=fa) { t=set[ch]; set[ch]=fa; ch=t; } return fa; } void mix(int x,int y) { int fx,fy; fx=find(x); fy=find(y); if(fx!=fy) set[fx]=fy; } void getmap() { int i,j,k=n; char a[2]; memset(a,' ',sizeof(a)); for(i=0;i<m;i++) { scanf("%s",a); if(a[0]=='U') { int b,c; scanf("%d%d",&b,&c); mix(vis[b],vis[c]); } else { int b; scanf("%d",&b); vis[b]=k; set[k]=k; k++; } } } void solve() { int i,ans=0; memset(mark,0,sizeof(mark)); for(i=0;i<n;i++) { int stem=find(vis[i]); if(!mark[stem]) { ans++; mark[stem]=1; } } printf("Case #%d: %d ",count++,ans); } int main() { count=1; while(scanf("%d%d",&n,&m)!=EOF) { init(); getmap(); solve(); } return 0; }