0011.共同祖先.md

11. 共同祖先

题目链接

C++

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

Java

import java.util.*;

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;
            int count1 = 0;
            while (map.containsKey(xiaoming)) {
                xiaoming = map.get(xiaoming);
                count1++;
            }
            int xiaoyu = 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");
            }
        }
    }
}

python

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

Go

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")
		}
	}
}

Js

// 引入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");
}

C

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