hihoCoder 1066 : 无间道之并查集

女爷i 2024-02-17 21:46 9阅读 0赞

#### \#1066 : 无间道之并查集 ####

时间限制: 20000ms

单点时限: 1000ms

内存限制: 256MB

##### 描述 #####

这天天气晴朗、阳光明媚、鸟语花香，空气中弥漫着春天的气息……额，说远了，总之，小Hi和小Ho决定趁着这朗朗春光出去玩。

但是刚刚离开居住的宾馆不久，抄近道不小心走入了一条偏僻小道的小Hi和小Ho就发现自己的前方走来了几个彪形大汉，定睛一看还都是地地道道的黑人兄弟！小Hi和小Ho这下就慌了神，捡肥皂事小，这一身百把来斤别一不小心葬身他乡可就没处说去了。

就在两人正举足无措之时，为首的黑叔叔从怀里掏出了一件东西——两张花花绿绿的纸，分别递给了小Hi和小Ho。

小Hi和小Ho接过来，只见上面写道（译为中文）：“本地最大的帮派——青龙帮，诚邀您的加入！”下面还详细的列出了加入青龙帮的种种好处。

于是两人略感心安，在同黑叔叔们交谈一番之后，已是均感相见恨晚。同时，在小Hi和小Ho表示自己不日便将回国之后，黑叔叔们也没有再提加入帮派之事，但是那为首的黑叔叔思索一会，开口道（译为中文）：“我现在有一个难题，思索了很久也没法子解决，既然你们俩都是高材生，不如来帮我看看。”

小Hi和小Ho点了点头表示没问题，于是黑叔叔继续说道：“这个问题是这样的，我们帮派最近混进了许多警察的卧底，但是在我们的调查过程中只能够知道诸如‘某人和另一个人是同阵营的’这样的信息，虽然没有办法知道他们具体是哪个阵营的，但是这样的信息也是很重要的，因为我们经常会想要知道某两个人究竟是不是同一阵营的。”

小Hi和小Ho赞同的点了点头，毕竟无间道也都是他们看过的。

黑叔叔接着说道：“于是现在问题就来了，我希望你们能写出这样一个程序，我会有两种操作，一种是告诉它哪两个人是同一阵营的，而另一种是询问某两个人是不是同一阵营的……既然你们就要回国了，不如现在就去我们帮派的总部写好这个程序再走把。”

为了生命安全与……小Hi和小Ho都不得不解决这个问题！那么他们究竟从何下手呢？

[提示：说起来其实就是不断的合并集合嘛~][Link 1]

##### 输入 #####

每个测试点（输入文件）有且仅有一组测试数据。

每组测试数据的第1行为一个整数N，表示黑叔叔总共进行的操作次数。

每组测试数据的第2~N+1行，每行分别描述黑叔叔的一次操作，其中第i+1行为一个整数op\_i和两个由大小写字母组成的字符串Name1\_i, Name2\_i，其中op\_i只可能为0或1，当op\_i=0时，表示黑叔叔判定Name1\_i和Name2\_i是同一阵营的，当op\_i=1时，表示黑叔叔希望知道Name1\_i和Name2\_i是否为同一阵营的。

对于100%的数据，满足N<=10^5, 且数据中所有涉及的人物中不存在两个名字相同的人（即姓名唯一的确定了一个人），对于所有的i，满足Name1\_i和Name2\_i是不同的两个人。

##### 输出 #####

对于每组测试数据，对于黑叔叔每次op\_i=1的操作，输出一行，表示查询的结果：如果根据已知信息（即这次操作之前的所有op\_i=0的操作），可以判定询问中的两个人是同一阵营的，则输出yes，否则输出no。

样例输入

10
    0 Steven David
    0 Lcch Dzx
    1 Lcch Dzx
    1 David Dzx
    0 Lcch David
    0 Frank Dzx
    1 Steven Dzx
    1 Frank David
    0 Steven Dzx
    0 Dzx Frank

样例输出

yes
    no
    yes
    yes

分析：并查集+map

AC代码：

#include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<map>
    using namespace std;
    const int maxn=1e5+10;
    int pre[maxn];
    string s1,s2;
    int N;
    map<string,int>mp;
    
    int find(int x){
    	int t=x;
    	while(t!=pre[t]){
    		t=pre[t];
    	}
    	/./将所有子节点挂在根结点上，提高效率
    	int i=x,j;
    	while(i!=t){
    		j=pre[i];
    		pre[i]=t;
    		i=j;
    	} 
    	return t;
    }
    
    void Union(int x,int y){
       int fx=find(x),fy=find(y);
       
       if(fx!=fy){
       	pre[fx]=fy;
       }	
    }
    
    int main(){
    	while(scanf("%d",&N)==1){
    		int cnt=0;
    		
    		for(int i=1;i<=N;i++)
    		pre[i]=i;
    		
    		for(int i=0;i<N;i++){
    			int q;
    			cin>>q>>s1>>s2;
    			int t1,t2;
    			if(mp.count(s1))t1=mp[s1];
    			else t1=mp[s1]=++cnt;
    			
    			if(mp.count(s2))t2=mp[s2];
    			else t2=mp[s2]=++cnt;
    			
    			if(q==1){
    			 	int fx=find(t1);
    			 	int fy=find(t2);
    			 	
    			 	if(fx==fy)printf("yes\n");
    			 	else printf("no\n");
    			}
    			else {
    				Union(t1,t2);
    			}
    		}
    	}
    	return 0;
    }

[Link 1]: https://hihocoder.com/problemset/problem/1066#