题目描述
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<algorithm> #include<map> using namespace std; const int N = 1e5+10; string s[N]; // dep 代表的是每个以i节点为根的子树的深(高)度 int dep[N]; // i的父亲节点是 fa[i] int fa[N]; void init() { for(int i=1;i<=100000;i++) { fa[i]=i; rank[i]=1; } } int find(int x) { return x == fa[x]?x:(fa[x]=find(fa[x])); } void merge(int i,int j) { // x是i的爹 ,y是j的爹 int x = find(i); int y = find(j); //这里是判断两棵树分别的深度 //将 深度小的树 往 深度大的树 上合并 //以免出现树越来高的情况 if(dep[x]<=dep[y]) fa[x] = y; else fa[y]=x; //如果两棵不同的树高度一样,那么随便谁合并谁都行,但是高度会加一(相当于加的是那个树的根) if(dep[x]==dep[y] && x!=y) { dep[y]++; } } // map 映射一下 字符串 -> [1,n]的数字 map<string,int>mp; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n,m,op; cin>>n>>m; string x,y; for(int i=1;i<=n;i++) cin>>s[i],mp[s[i]]=i,fa[i]=i,dep[i]=1; while(m--) { cin>>op>>x>>y; if(op == 1) { merge(mp[x],mp[y]); }else { int i = find(mp[x]); int j = find(mp[y]); cout<<(i==j?1:0)<<endl; } } return 0; }
