题解 | #DongDong认亲戚#
DongDong认亲戚
https://ac.nowcoder.com/acm/problem/23803
链接：https://ac.nowcoder.com/acm/contest/22904/1021
来源：牛客网
来源：牛客网
题目描述
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操作给予回答
思路：用map映射+并查集+string函数做
注：string函数定义需要在using namespace std;语句的后面定义哦
代码如下：
#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
map<string,string>father; //map映射
string find(string x){ //查找函数
if(father[x]==x) return x;
else return father[x]=find(father[x]);
}
void merge(string x,string y){ //合并函数
if(find(x)!=find(y)) father[find(x)]=find(y);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n,m,opt;
string s,a,b;
cin>>n>>m;
for(int i=0;i<n;i++){
cin>>s;
father[s]=s;//初始化父节点
}
while(m--){
cin>>opt>>a>>b;
if(opt==1){
merge(a,b);//合并a与b，使其变为一个集合
}
if(opt==2){
if(find(a)==find(b)) printf("1\n"); //a和b对应的父节点相同就输出1，不同就输出0
else printf("0\n");
}
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
map<string,string>father; //map映射
string find(string x){ //查找函数
if(father[x]==x) return x;
else return father[x]=find(father[x]);
}
void merge(string x,string y){ //合并函数
if(find(x)!=find(y)) father[find(x)]=find(y);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n,m,opt;
string s,a,b;
cin>>n>>m;
for(int i=0;i<n;i++){
cin>>s;
father[s]=s;//初始化父节点
}
while(m--){
cin>>opt>>a>>b;
if(opt==1){
merge(a,b);//合并a与b，使其变为一个集合
}
if(opt==2){
if(find(a)==find(b)) printf("1\n"); //a和b对应的父节点相同就输出1，不同就输出0
else printf("0\n");
}
}
return 0;
}
注：cin不要和scanf混用，会出现意外情况，比如把代码中的cin>>n>>m改成scanf("%d %d",&n,&m);看上去是一样的，但实际上会出现错误，通过率为0%，当时这里卡了好久qwq
算法入门班习题题解&感悟 文章被收录于专栏
这是本人对于算法入门班共十三章习题的题解与个人的一些感悟，本人写题解的目的是对于某些经典的/陌生的/无从下手的/思维方向错误的题目加深印象。 希望自己能够在学习算法的路上走得更远，今天也是努力学习的一天!
投递牛客等公司