L2-016愿天下有情人都是失散多年的兄妹
时间限制200ms内存限制64MB
题目描述：呵呵。大家都知道五服以内不得通婚，即两个人最近的共同祖先如果在五代以内则不可通婚。本题就请你帮助一对有情人判断一下，他们究竟是否可以成婚？
输入格式：输入第一行给出一个正整数N，随后N行，每行按以下格式给出一个人的信息：
本人ID性别父亲ID母亲ID
其中ID是5位数字，每人不同；性别M代表男性、F代表女性。如果某人的父亲或母亲已经不可考，则相应的ID位置上标记为-
接下来给出一个正整数K，随后K行，每行给出一对有情人的ID，其间以空格分隔。
注意：题目保证两个人是同辈，每人只有一个性别，并且血缘关系网中没有乱伦或隔辈成婚的情况。
输出格式：对每一对有情人，判断他们的关系是否可以通婚：如果两人是同性，输出NeverMind；如果是异性并且关系出了五服，输出Yes；如果异性关系未出五服，输出No。
输入样例：2400001M01111-100002F022220333300003M022220333300004F044440333300005M044440555500006F044440555500007F066660777700008M066660777700009M000010000200010M000030000600011F000050000700012F000080888800013F000090001100014M000100999900015M000100999900016M100000001200017F-10001200018F110000001300019F111000001800020F000151111000021M111000002000022M00016-100023M100120001700024M00022100139000210002400019000240001100012000220001800001000040001300016000170001500019000210001000011
就是给你nnn个人，并告诉你这nnn个人中第iii个人的编号，性别，父亲编号，母亲编号
我们可以想象的是把自己当作一个根节点，父母当作子节点的去遍历
然后呢，需要判断当前这个节点有没有被用过，用过则是五服之内的
怎么知道是大于五服呢，也就是当前这个人遍历超过4次的第4次正好是五服
↑这样5和7就是五服之内
↑这样子6和7就是五福之外了
↑这样子6和7也是五福之外的
import java.io.*;
import java.math.*;
import java.util.*;
public class Main
{
static int N = (int) 1e5;
// 存储当前节点i的父母节点
static ArrayList<Integer> fa[] = new ArrayList[N + 10];
// 存储当前节点的性别
static String sex[] = new String[N + 10];
// 存储当前节点是否被用过
static boolean vis[] = new boolean[N + 10];
static boolean check = true;
static void dfs(int u, int depth)
{
// 大于等于4的话 就是超过五服的了
// 不需要再次去遍历当前节点的子节点了
if (depth >= 4)
return;
// 遍历当前节点的子节点
for (int i : fa[u])
{
// 如果当前节点走过
if (vis[i])
{
check = false;
return;
}
// 将当前节点标记为走过
vis[i] = true;
// 继续遍历当前节点下的节点 且深度+1
dfs(i, depth + 1);
}
}
public static void main(String[] args) throws IOException
{
for (int i = 0; i <= N; i++)
fa[i] = new ArrayList<Integer>();
int n = sc.nextInt();
for (int i = 1; i <= n; i++)
{
int id = sc.nextInt();
sex[id] = sc.next();
int father = sc.nextInt(), mother = sc.nextInt();
if (father != -1)
{
sex[father] = "M";
fa[id].add(father);
}
if (mother != -1)
{
sex[mother] = "F";
fa[id].add(mother);
}
}
int k = sc.nextInt();
while (k-- > 0)
{
int a = sc.nextInt(), b = sc.nextInt();
// 两个人同性
if (sex[a].equals(sex[b]))
{
out.println("Never Mind");
continue;
}
Arrays.fill(vis, false);
check = true;
dfs(a, 0);
dfs(b, 0);
out.println(check ? "Yes" : "No");
}
out.flush();
out.close();
}
static Scanner sc = new Scanner(System.in);
static PrintWriter out = new PrintWriter(System.out);
}
树的深度dfs
如果有说错的或者不懂的尽管提嘻嘻
一起进步！！！
文章为作者独立观点，不代表股票量化交易软件接口观点