链接:https://ac.nowcoder.com/acm/problem/23803
来源:牛客网

题目描述
DongDong每年过春节都要回到老家探亲,然而DongDong记性并不好,没法想起谁是谁的亲戚(定义:若A和B是亲戚,B和C是亲戚,那么A和C也是亲戚),她只好求助于会编程的你了。

输入描述:
第一行给定n,m表示有n个人,m次操作

第二行给出n个字符串,表示n个人的名字分别是什么(如果出现多个人名字相同,则视为同一个人)(保证姓名是小写字符串)

接下来m行,每行输入一个数opt,两个字符串x,y

当opt=1时,表示x,y是亲戚

当opt=2时,表示询问x,y是否是亲戚,若是输出1,不是输出0

数据范围:1<=n,m<=20000,名字字符长度小等于10
输出描述:
对于每个2操作给予回答
示例1
输入
4 4
chen lin yi cheng
2 chen lin
1 chen lin
1 yi lin
2 yi lin
输出
0
1

解:并查集模板题,熟悉即可。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
using namespace std;
map<string,int> dic;
int lst[20010];
int find(int x)
{
    if (x!=lst[x])
    {
        return lst[x]=find(lst[x]);
    }
    return lst[x];

}
int main()
{
    int n,m;
    cin>>n>>m;
    for (int i=1;i<=n;i++)
    {
        string name;
        cin>>name;
        lst[i]=i;
        dic[name]=i;
    }

    for (int i=1;i<=m;i++)
    {   
        int x;
        string a,b;
        cin>>x>>a>>b;
     if (x==2)
     {

        if (find(dic[a])==find(dic[b]))
        cout<<1<<endl;
        else
        cout<<0<<endl;
     }
     else if (x==1)
     {
         lst[find(dic[b])]=find(dic[a]);
     }
    }  
    system ("pause");
    return 0;
}