nyoj 1022 合纵连横（经典并查集=---删点操作）

痛定思痛。 2024-02-17 20:55 24阅读 0赞

### 合纵连横 ###

时间限制： 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

具体做法可以参考 ： http://blog.csdn.net/a915800048/article/details/41703865 讲的非常清晰明了

AC代码：

#include<cstdio>
    #include<cstring>
    using namespace std;
    const int maxn=1e5+10;
    int pre[maxn];
    int box[maxn<<1];
    int mark[maxn<<1];
    int n,m;
    
    int find(int x){
    	int t=x;
    	while(t!=box[t]){
    		t=box[t];
    	}
    	
    	//这里是路径压缩，就是把所有节点直接挂在根节点上，不要这步也行，查询效率低点 
    	int i=x,j;
    	while(i!=t){
    		j=box[i];
    		box[i]=t;
    		i=j;
    	}
    	return t;
    }
    
    void Union(int x,int y){
    	int fx=find(x),fy=find(y);
    	if(fx!=fy){
    		box[fx]=fy;
    	}
    }
    
    int main(){
    	int count=0;
    	while(scanf("%d%d",&n,&m)==2){
    		for(int i=0;i<n;i++)
    		{
    			pre[i]=i;
    		    box[i]=i;
    		}
    		    
    		int tol=n;
    		for(int i=0;i<m;i++){
    			char ch;
    			int x,y; //刚开始x,y都不小心定义成了char, Runtime好几次，这错误真找了半天！！！ 
    			getchar();
    			scanf("%c",&ch);
    			if(ch=='U'){
    				scanf("%d%d",&x,&y);
    				Union(pre[x],pre[y]);
    			}
    			else {
    				scanf("%d",&x);
    				pre[x]=tol;
    				box[tol]=tol;
    				tol++;
    			}
    		}
    		
    		memset(mark,0,sizeof(mark));
    		for(int i=0;i<n;i++)
    		{
    			int tmp=find(pre[i]);
    			mark[tmp]++;
    		}
    		
    		int cnt=0;
    		for(int i=0;i<tol;i++)
    		if(mark[i])cnt++;
    			
    		printf("Case #%d: %d\n",++count,cnt);	
    	}
    	return 0;
    }