思路:并查集模版题

不妨把每个亲友团认为是一个集合,那么并查集中的并即合并两个集合(有共同亲戚的要在同一个亲友团),查即找两个人有没有在一个集合(亲友团)

AC代码:

#include<iostream>
#include<unordered_map>//也可以将所有的unordered_map替换为map,但运行时间有所延长
using namespace std;
int fa[20010];
unordered_map<string,int> mp;//将人名映射成数字,因为此处不需要按照顺序遍历元素,所以可以用无序map
inline int find(int x)
{
  //如果他的父亲是自己,证明他是根,否则更新(搜索)他的父亲,直到find到了根节点,再返回(有递归思想在里面).这样不仅实现了查找到最根的节点,还实现了路径压缩,每次查找都在把查找路径上的所有点"连在了"他的最根节点上
    return x==fa[x]? x : fa[x]=find(fa[x]);//***//
}
inline void merge(int x,int y)
{
    
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    int n,m,opt;
    string s,x,y;
    cin>>n>>m;
    for(int i=1;i<=n;++i)
    {
        fa[i]=i;//新建每棵子树,方便后续合并和查找
        cin>>s;
        mp[s]=i;//将人名映射成数字
    }
    for(int i=1;i<=m;++i)
    {
        cin>>opt>>x>>y;
        if(opt==2) 
        {
            if(find(mp[x])==find(mp[y])) {cout<<"1\n";}//根节点相同
            else {cout<<"0\n";}
        }
        else  {fa[find(x)]=find(y);}//**//合并两棵"树",即把其中一棵树的最根节点连在(的父亲认为是)另一棵树的最根节点上
    }
    return 0;
}

AC代码2(少一个map映射字母到数字,直接将某个点映射到他的父亲)(由于map中两个对象都是string,实际时间与空间占用均更高):

#include<iostream>
#include<unordered_map>
using namespace std;
unordered_map<string,string> fa;
inline string find(string x)
{
    return x==fa[x]? x : fa[x]=find(fa[x]);
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    int n,m,opt;
    string s,x,y;
    cin>>n>>m;
    for(int i=1;i<=n;++i)
    {
        cin>>s;
        fa[s]=s;
    }
    for(int i=1;i<=m;++i)
    {
        cin>>opt>>x>>y;
        if(opt==2) 
        {
            if(find(x)==find(y)) {cout<<"1\n";}
            else {cout<<"0\n";}
        }
        else  fa[find(x)]=find(y);
    }
    return 0;
}