L2-016 愿天下有情人都是失散多年的兄妹（DFS）

题目链接

https://pintia.cn/problem-sets/994805046380707840/problems/994805061769609216

思路

我们把这个家族关系看成一颗二叉树，树的根节点是子元素，“左儿子” 是父亲，“右儿子” 是母亲，然后我们定义 i s m a n [ i ] isman[i] isman[i] 如果为 true 表示编号为id 的性别为男，反之为女，然后我们每次输入一行数据就连边，起点是当前编号，终点是父母编号（存在的话），然后我们在Q 次询问的时候，首先判断两个编号是否为异性，然后我们将以当前编号为起点的长度小于等于 5 5 5 的所有的点全部放入一个 set中，另一个人同理，我们只需要遍历其中一个set然后在另一个set中查找是否存在当前的元素，即可判断是否5代内有交集，如果没有交集的话就输出Yes 否则输出No

代码

#include
using namespace std;
#define ll long long
#define mod 1000000007
#define endl "\n"
#define PII pair
#define INF 0x3f3f3f3f

const int N = 1e5+10;

int n,q;
vector V[N];
bool isman[N];

void dfs(int id,int deep,set &ans) {
	if(deep == 6) return;
	ans.insert(id);
	for(auto it : V[id])
		dfs(it,deep + 1,ans);
}

void slove(int l,int r){
	if(isman[l] == isman[r]){
		cout>l>>r;
		slove(l,r);
	}
	return 0;
}