描述
乱世天下，诸侯割据。每个诸侯王都有一片自己的领土。但是不是所有的诸侯王都是安分守己的，实力强大的诸侯国会设法吞并那些实力弱的，让自己的领土面积不断扩大。而实力弱的诸侯王为了不让自己的领土被吞并，他会联合一些其他同样弱小的诸侯国，组成联盟(联盟不止一个)，来共同抵抗那些强大的诸侯国。 强大的诸侯国为了瓦解这些联盟，派出了最优秀的间谍来离间他们，使一些诸侯国退出联盟。最开始，每个诸侯国是一个联盟。
有两种操作
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解题链接(http://blog.csdn.net/a915800048/article/details/41703865)
C语言AC代码：
时间语言结果内存192CAccepted3752 #include<stdio.h> #include<string.h> int per[300000],v[300000],mark[300000],n;// 数组开大，越大越好，否则出现RuntimeError void init()//初始化 { for(int i=0;i<n;++i) { per[i]=i; v[i]=i; } } int find(int x)//查找 { int r=x; while(r!=per[r]) { r=per[r]; } int i=x,j; while(i!=r)//经典的路径压缩 { j=per[i]; per[i]=r; i=j; } return r; } void join(int x,int y)//合并 { int fx=find(x),fy=find(y); if(fx!=fy) { per[fy]=fx; } } int main() { int t=0,i,m,a,b,k;char s; while(~scanf("%d%d",&n,&m)) { init();k=n;//现在k指的位置处空白 memset(mark,0,sizeof(mark)); for(i=0;i<m;++i) { scanf(" %c",&s); if(s=='U') { scanf("%d%d",&a,&b); join(v[a],v[b]); } else { scanf("%d",&a); v[a]=k;//标记转移到的位置， per[k]=k;//把这个位置处保存上他的操作编号（下标） ++k;//k指向下一个空白处 } } int cnt=0; for(i=0;i<n;++i) { int temp=find(v[i]);//找根节点 if(!mark[temp])//如果根节点没出现过 { mark[temp]=1;//标记 ++cnt;//累加 } } printf("Case #%d: %d\n",++t,cnt);//按格式输出 } return 0; }
