链接: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; }