11. 共同祖先

#include<iostream>
#include<vector>
using namespace std;
int main() {
    int n, a, b;
    vector<int> nums = vector<int>(30, 0); // 使用数组来记录映射关系，初始化为0
    while (cin >> n) {
        while (n--) {
            cin >> a >> b;
            nums[a] = b; // 记录映射关系
        }
        int len_ming = 0, len_yu = 0;
        int ming = nums[1];// 小明编号为1 
        while (ming != 0) { // 当ming 为0 的时候，说明找到了祖先了 
            ming = nums[ming];
            len_ming++; // 记录小明找到祖先的长度
        }
        int yu = nums[2]; // 与小明同理
        while (yu != 0) {
            yu = nums[yu];
            len_yu++;
        }
        if (len_ming > len_yu) cout << "You are my elder" << endl;
        else if (len_ming == len_yu) cout << "You are my brother" << endl;
        else cout << "You are my younger" << endl;
    }
}

import java.util.*;

//[方法一] 使用 HashMap 保存映射关系
public class Main{
    static Map<Integer, Integer> map = new HashMap();	//使用哈希表来记录父子之间的映射关系
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextInt()) {
            int n = sc.nextInt();
            for (int i = 0; i < n; i++) {
                int a = sc.nextInt();
                int b = sc.nextInt();
                map.put(a, b);	//往哈希表中插入一条关系记录
            }
            int xiaoming = 1;	//小明编号值：1
            int count1 = 0;		//记录从公共祖先到小明一路上一共要经过多少代
            //公共祖先不存在父亲，哈希表中不存在以公共祖先编号为key的记录
            while (map.containsKey(xiaoming)) {
                xiaoming = map.get(xiaoming);	//不断向上寻找，直至找到公共祖先
                count1++;	//记录小明到公共祖先的长度
            }
            int xiaoyu = 2;		//小宇编号值：2（与小明同理）
            int count2 = 0;
            while (map.containsKey(xiaoyu)) {
                xiaoyu = map.get(xiaoyu);
                count2++;
            }
            if (count1 < count2) {
                System.out.println("You are my younger");
            } else if (count1 > count2){
                System.out.println("You are my elder");
            } else {
                System.out.println("You are my brother");
            }
        }
    }
}

//[方法2] 使用数组保存映射关系
public class Main{
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNextLine()){
            int count = Integer.parseInt(sc.nextLine());
            //parent[i]：编号为 i 的人的父亲是 parent[i]。例如 3 的父亲是 5，则有 parent[3]=5
            int[] parent = new int[21];		//根据题意，编号取值范围: [1,20]
            while(count-- > 0){
                String[] inputs = sc.nextLine().split(" ");
                int son = Integer.parseInt(inputs[0]);	//输入的关系对(a,b)中 a 为儿子
                int father = Integer.parseInt(inputs[1]);	//b 为父亲
                parent[son] = father;	//将父子关系保存到 parent 数组中
            }
            //调用类内方法分别计算出从公共祖先到小明或小宇要经过多少代
            int depth_XM = Main.findDepth(parent,1),depth_XY = Main.findDepth(parent,2);
            if(depth_XM > depth_XY){
                System.out.println("You are my elder");
            }else if(depth_XM == depth_XY){
                System.out.println("You are my brother");
            }else{
                System.out.println("You are my younger");
            }
        }
        sc.close();
        return;
    }
    
    /**
    * desc：找出从公共祖先开始到给定编号的人 son 所经过的代数
    */
    public static int findDepth(int[] parent,int son){
        int count = 0;
        //只有从公共祖先到当前编号，只有祖先一个人在parent数组中的取值为初始值 0
        while(parent[son] != 0){
            //当前编号的父亲不是公共祖先，需要继续往上寻找父亲的父亲，知道找到公共祖先
            son = parent[son];
            count += 1;
        }
        return count;	//返回从公共祖先到 son 所经过的代数
    }
}

def find_ancestor(person, father):
    ancestors = []
    while person in father:
        person = father[person]
        ancestors.append(person)
    return ancestors
 
 
while True:
    try:
        N = int(input())
        father = {}
        for _ in range(N):
            a, b = map(int, input().split())
            father[a] = b
        ming_ancestors = find_ancestor(1, father)
        yu_ancestors = find_ancestor(2, father)
        if 1 in yu_ancestors:
            print("You are my younger")
        elif 2 in ming_ancestors:
            print("You are my elder")
        else:
            if len(ming_ancestors) > len(yu_ancestors):
                print("You are my elder")
            elif len(ming_ancestors) < len(yu_ancestors):
                print("You are my younger")
            else:
                print("You are my brother")
    except:
        break

package main

import (
	"fmt"
)

func main() {
	var n, a, b, li, yu int
	nums := make([]int, 30)

	for {
		_, err := fmt.Scanf("%d", &n)
		if err != nil {
			break
		}

		for i := 0; i < n; i++ {
			fmt.Scanf("%d %d", &a, &b)
			nums[a] = b
		}

		lenli := 0
		lenyu := 0
		li = nums[1]
		for li != 0 {
			li = nums[li]
			lenli++
		}

		yu = nums[2]
		for yu != 0 {
			yu = nums[yu]
			lenyu++
		}

		if lenli > lenyu {
			fmt.Println("You are my elder")
		} else if lenli == lenyu {
			fmt.Println("You are my brother")
		} else {
			fmt.Println("You are my younger")
		}
	}
}

// 引入readline模块来读取标准输入
const readline = require('readline');

// 创建readline接口
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

let parent = new Array(21).fill(0);
let n;
rl.on('line', (input) => {
    // 读入每行数据，将其转换为数组
    const readline = input.split(' ').map(Number);
    if (readline.length === 1) {
        n = readline[0]
    } else {
        const [a, b] = readline
        parent[a] = b
        n--
        if (n === 0) {
            getAnswer(parent)
        }
    }
});

function getAnswer(parent) {
    let len_ming = 0;
    let len_yu = 0;
    let ming = parent[1];  // 小明的编号为1
    while (ming !== 0) {
        len_ming++;
        ming = parent[ming]; // 继续遍历其父节点得到距离祖先的长度
    }
    // 小宇同理
    let yu = parent[2];
    while (yu !== 0) {
        len_yu++;
        yu = parent[yu];
    }
    if (len_ming > len_yu) console.log("You are my elder");
    else if (len_ming < len_yu) console.log("You are my younger");
    else console.log("You are my brother");
}

#include <stdio.h>

int main() {
    int n, a, b, li, yu;
    int nums[30] = {0}; // 使用数组来记录映射关系，初始化为0
    while (scanf("%d", &n) == 1) {
        while (n--) {
            scanf("%d%d", &a, &b);
            nums[a] = b; // 记录映射关系
        }
        int lenli = 0, lenyu = 0;
        li = nums[1]; // 小明编号为1 
        while (li != 0) { // 当li 为0 的时候，说明找到了祖先了 
            li = nums[li];
            lenli++; // 记录小明找到祖先的长度
        }
        yu = nums[2]; // 与小明同理
        while (yu != 0) {
            yu = nums[yu];
            lenyu++;
        }
        if (lenli > lenyu) printf("You are my elder\n");
        else if (lenli == lenyu) printf("You are my brother\n");
        else printf("You are my younger\n");
    }
    return 0;
}