DongDong认亲戚

一、题目大意:

题目描述

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操作给予回答

二、题意分析:

哎呀嘛,这几天由于学校内事情繁杂导致几天都没有更新博客了,今天就小熬一会儿来写一篇博客.先闲聊几句,正好这几天正在复习并查集专题,感觉并查集这个数据结构太有魅力了,太爱这个数据结构了.所以今天就带来了关于该数据结构在算法竞赛中的一个模板题.

其实该题就是个并查集的模板题,还是个老话题,遇到算法题时首先得识别出来该题是考察哪一类算法或者思想.不妨咱们一起来分析分析该题.首先我们先思考思考为什么该题会用到并查集.若A和B是亲戚,B和C是亲戚,那么A和C也是亲戚,这不就和并查集中合并操作的算法思想很相似不是吗?还有就是后续询问某两个人是否是亲戚,这不就和并查集的查询操作很类似的吗?因此选择使用并查集这个数据结构来解决该题.当然还有一个小小的注意点,可以简化代码.因为并查集是通过树的形式来存储数据的,但是输入的数据又是字符串,不是整型,那么其实我们可以通过map这个数据结构来将字符串映射为数字便于后续数据的存储.

三、代码分析:

经过上述分析后我想各位应该对该题的求解有了一定的思路.看看AC代码吧.

using namespace std;

int n,m,opt,father[20010]; //father --》 存储每个点的根节点
map<string,int> mp; //将字符串映射为数字 --》 map存储数据
string s1,s2;
int find(int x){ //寻找某一节点的根节点(路径压缩)
    return father[x] == x ? x : father[x] = find(father[x]);
}
void merge(int x,int y){ //合并操作
    father[find(x)] = find(y);
}
int main(){
    scanf("%d%d",&n,&m);
    for (int i = 1;i <= n;i++){ //n个亲戚
        cin >> s1;
        mp[s1] = i;
        father[i] = i; //最开始标记自己为根节点
    }
    for (int i = 1;i <= m;i++){ //m次操作
        cin >> opt >> s1 >> s2;
        if (opt == 1) merge(mp[s1],mp[s2]);
        else{
            if (find(mp[s1]) != find(mp[s2])) cout << 0 << endl;
            else cout << 1 << endl;
        }
    }
    
    return 0;
}

四、写在后面:

任何事情开始的学习都会很痛苦的,只要熬过这段时间我们一定能成为更棒的自己.星光不负赶路人,各位一起加油吧.