题解：P10124 [USACO18OPEN] Family Tree B

· · 题解

废话时间

我不会橙我不会橙我不会橙我不会橙我不会橙。

正文

剖析题目

给一棵树（或者森林），求出给定的两个点之间的关系。

思路

原本我是想用 LCA 来做的，但是看了一眼题解，用 LCA 的大佬太多了，所以用这样一个非常暴力的做法。

在处理情况之前，因为输入都是字符串类型，所以可以考虑使用 map 映射出每个字符串唯一对应的整型，这样便于存图。存图的方法我用了邻接表，而且是由母亲向孩子建的有向边。

首先处理 NOT RELATED 的情况。这意味着输入的图是森林，而要查询的两只牛在不同的树中。这一点很简单，可以用并查集实现。

然后用一个 dfs 处理每个点的深度，方便后面的操作。

先处理直系亲属的情况。直系亲属情况很好办，可以从深度较深的那个点往上找。若找到另一个要查询的点，则说明二者存在直系亲属关系，输出若干 great- 后输出 grand-mother 就可以了。需要注意的是，也有可能不必输出grand 直接输出 mother 即可。

如果找不到直系亲属，那么还有 SIBLINGS，COUSINS，(great-great...) aunt 三种情况。可以先从最简单的姐妹关系入手。

处理姐妹关系时，由于每个点的母亲是唯一且确定的，我们可以开一个数组来记录每个节点的母亲。如果要查询的两个节点的母亲为同一个，那么此时直接输出 SIBLINGS。

再处理旁系亲属的情况。可以遍历深度较深点的直系亲属的孩子。如果在这些孩子中有要查询的另一个点，那么可以确定为旁系亲属关系，输出 (great-great...) aunt。

如果以上情况都不是，输出 COUSINS。

简化一下。

思路就这样理清了，代码还是有一点难调的。

代码

一段段来看。

首先 now 参数指的是当前处理到了哪个节点。sum 参数指的是要查询的点的深度差。这一点也可以直接使用 deep 数组内的值相减得到。

if(fa[now]==0)return ; 的作用是防止搜到最顶上的节点从而无限递归，造成 RE。 这个也需要解释吗？

完整代码

#include<bits/stdc++.h>
using namespace std;
const int N=2e2+5;
map<string,int> mp;//用 map 映射节点
string temp_a,temp_b;
string a,b;
vector<int> vec[N];
int deep[N],n,id,fa[N],sum,fat[N];
int finds(int x){
    return x==fat[x]?x:fat[x]=finds(fat[x]);
}
//处理深度
void dfs_deep(int id,int dep){
    if(deep[id]!=0)return ;
    deep[id]=dep;
    for(int i=0;i<vec[id].size();i++)
        dfs_deep(vec[id][i],dep+1);
    return ;
}
//找直接亲属 
void dfs_1(int now,int sum){
    if(mp[a]==now){
        cout<<a<<" is the ";
        int flag=sum>1?1:0;
        sum-=2;
        while(sum>0)cout<<"great-",sum--;
        if(flag==1)cout<<"grand-";
        cout<<"mother of "<<b;
        exit(0);
    }
    if(fa[now]==0)return ;
    dfs_1(fa[now],sum+1);
    return ;
}
//找旁系亲属 
void dfs_2(int now,int sum){
    for(int i=0;i<vec[now].size();i++){
        if(vec[now][i]==mp[a]){
            cout<<a<<" is the "; 
            sum-=3;
            while(sum>=0)cout<<"great-",sum--;
            cout<<"aunt of "<<b;
            exit(0);
        }
    } 
    if(fa[now]==0)return ;
    dfs_2(fa[now],sum+1);
    return ;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>a>>b;
    for(int i=1;i<=N;i++)fat[i]=i;
    mp[a]=++id,mp[b]=++id;
    for(int i=1;i<=n;i++){
        cin>>temp_a>>temp_b;
        if(mp[temp_a]==0)mp[temp_a]=++id;
        if(mp[temp_b]==0)mp[temp_b]=++id;
        vec[mp[temp_a]].push_back(mp[temp_b]);//可以看到这里只有母亲向孩子建边，是有向边。
        fa[mp[temp_b]]=mp[temp_a];//并查集
        int fax=finds(mp[temp_a]),fay=finds(mp[temp_b]);
        if(fax!=fay)fat[fay]=fax;

    }
    for(int i=1;i<=id;i++){
        if(fa[i]==0){
            dfn(i,1);
            break;
        }
    }
    //没有关系
    if(finds(mp[a])!=finds(mp[b])){
        cout<<"NOT RELATED";
        return 0;
    }
    //姐妹关系 
    if(fa[mp[a]]==fa[mp[b]]){
        cout<<"SIBLINGS";
        return 0;
    }
    if(deep[mp[a]]>deep[mp[b]])
        swap(a,b);
    dfs_1(mp[b],0);
    dfs_2(mp[b],0);
    //不是前面任何一种关系，则为表姐妹关系
    cout<<"COUSINS";
    return 0;
}

代码就是这个样子，有一点值得注意。题目中的 n 代指的是有多少种关系，而非有多少个点。所以开数组的时候只开 100 是不够的。

最后：祝 CSP J/S 2024 RP++ ！

感谢阅读。