华为机试题-养猪场防疫

本文主要是介绍华为机试题-养猪场防疫，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

老李在多年前承包了一个养猪场,并引入了若干只种猪,经过这些年的经营,现在养猪场有
N 只猪,编号从 0 到 N-1(每只猪无论生死都有唯一的编号);老李在每只猪生产的时候记下了生产的母猪和出生的小猪,格式:x y1 y2 y3…([注:x 为猪妈妈，y1、 y2、y3….为新生的猪惠,以上编码均在 0…N-1 内,每只猪可以多次生产,每个猪崽只有一个猪妈妈);
为了防疫需要,要检查任意两只猪是否有亲戚关系(两只猪具有相同的祖先),并计算出关系亲疏情况(关系距离,相同编号距离为 0). 解答要求
时间限制:CIC++1000ms.其他语言:2000ms 内存限制:CIC++ 256MB,其他语
言:512MB
输入
第一行输入总数 N
第二行表示后续生产记录行数 M, 后续 M 行输入生产记录,以空格分隔 x y1 y2 y3
最后一行输入 m1, m2:表示待检查的 m1 和 m2 编号【取值范围】
0<N<=1000000000 0<=M<10000
输出
一个整数,表示 m1 和 m2 之间的关系距离,无亲戚关系输出-1
样例 1
输入:
3
1
0 1 2
0 1
输出:1
解释:0 号生产了 1 号和 2 号
所以 0 号和 1 号是有亲戚关系(0-1),且关系距离为 1

参考代码

整体思路使用map来存储关系，一开始看以为是并查集，但是并查集只能判断是不是亲戚关系，不太好计算关系的距离，如果有大佬可以按照并查集的思路，麻烦写在评论区，感谢！！！

package RealTest;/*** @ClassName PigRelationship* @Description TODO* @Author 21916* @Date 2024/3/13 20:58*/import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;public class PigRelationship {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int N = Integer.parseInt(scanner.nextLine()); // 猪的总数int M = Integer.parseInt(scanner.nextLine()); // 母子关系的数量Map<Integer, Integer> pigsMum = new HashMap<>(); // 猪的母亲映射for (int i = 0; i < M; i++) {System.out.println("请输入第" + (i + 1) + "行的数据，母亲编号和儿子编号以空格分隔，结束后按Enter键:");String line = scanner.nextLine(); // 读取整行输入String[] parts = line.trim().split("\\s+"); // 使用空格分割字符串if (parts.length < 2) {System.out.println("错误：每行至少需要一个母亲编号和一个儿子编号。");continue; // 如果输入不符合要求，跳过当前行并继续下一行}int pigMum = Integer.parseInt(parts[0]); // 母亲编号for (int j = 1; j < parts.length; j++) { // 从第二个元素开始遍历，它们是儿子编号int pigSon = Integer.parseInt(parts[j]); // 儿子编号System.out.println("pigSon: " + pigSon);pigsMum.put(pigSon, pigMum); // 将儿子映射到母亲}}System.out.println("输入完成了");// 将没有儿子的猪（可能是母亲）映射到-1for (int i = 0; i < N; i++) {if (!pigsMum.containsKey(i)) {pigsMum.put(i, -1);}}int m1 = scanner.nextInt(); // 第一只猪的编号int m2 = scanner.nextInt(); // 第二只猪的编号Map<Integer, Integer> distance = new HashMap<>(); // 存储猪到m1的距离映射int tmp = m1;int d = 0;// 从m1向上遍历到m2或根节点while (tmp != -1) {if (tmp == m2) {System.out.println(d);scanner.close();return;} else {distance.put(tmp, d);d++;tmp = pigsMum.getOrDefault(tmp, -1); // 如果找不到映射，返回-1System.out.println("tmp"+tmp);}}tmp = m2;d = 0;// 从m2向上遍历，查看是否能找到与m1共享的祖先while (tmp != -1) {if (distance.containsKey(tmp)) {System.out.println(d + distance.get(tmp));scanner.close();return;} else {d++;tmp = pigsMum.getOrDefault(tmp, -1); // 如果找不到映射，返回-1}}System.out.println(-1); // 如果没有共享祖先，输出-1scanner.close();}
}