# hihoCoder 1066-无间道之并查集

hihoCoder 1066-无间道之并查集
#1066 : 无间道之并查集

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

UNION操作就是已知元素c和d，要把这两个元素所在的集合合并起来，自然就是先用FIND找到c和d的祖先，然后把其中一个祖先当做另一个祖先的祖先，这样就把两个集合合并起来了。

```#include<iostream>
#include<string>
#include<map>
using namespace std;
map<string,string> represent;
//并查集FIND操作
string find_represent(string name)
{
if(name==represent[name])
return name;
else
{
represent[name]=find_represent(represent[name]);//把经过的节点全部链接到根节点
return represent[name];
}
}
int main()
{
//freopen("input.txt","r",stdin);
int n;
int op;
string name1,name2;
cin>>n;
while(n--)
{
cin>>op>>name1>>name2;
if(op==0)
{
if(represent.find(name1)==represent.end())
represent[name1]=name1;
if(represent.find(name2)==represent.end())
represent[name2]=name2;
represent[find_represent(name1)]=find_represent(name2);//UNION操作
}
else
{
//**********也需要先判断是否在map里*********
if(represent.find(name1)==represent.end())
represent[name1]=name1;
if(represent.find(name2)==represent.end())
represent[name2]=name2;
//******************************************
if(find_represent(name1)==find_represent(name2))
cout<<"yes"<<endl;
else
cout<<"no"<<endl;
}
}
return 0;
}
```

```if(name==represent[name])
```

This site uses Akismet to reduce spam. Learn how your comment data is processed.