自动搬运

查看原文

来自洛谷，原作者为

	Colubrid_L 且将新火试新茶，诗酒趁年华

搬运于2025-08-24 22:54:55，当前版本为作者最后更新于2024-10-07 17:37:01，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

废话时间

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

正文

剖析题目

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

思路

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

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

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

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

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

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

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

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

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

简化一下。

• 判断为没有关系：使用并查集。
• 判断为姐妹关系：同一个母亲。
• 判断为直系亲属：按深度较深往深度较浅搜。
• 判断为旁系亲属：搜直系亲属的孩子。
• 判断为表姐妹关系：不是以上四种关系。

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

代码

一段段来看。

• 首先，处理深度。

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 ;
}

• 判断为没有关系我使用了并查集。代码就不给了，因为很简单。
• 然后是判断姐妹关系。在程序中我使用了 fa 这个数组来存储每个节点的母亲，所以如果要查询的两个点的母亲相同，则在 fa 数组中，两个节点为下标的值相同。
• 判断为直系亲属关系。

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 ;
}

来理解一下这段代码的意思。

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

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

• 判断为旁系亲属关系。

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 ;
}

参数的意义同找直系亲属时参数的意义。

• 找表姐妹关系。如果执行完以上代码仍然没有找到关系，那么确定为表姐妹关系，直接输出就可以了。

完整代码

#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++ ！

感谢阅读。