11. 共同祖先

时间限制：1.000S 空间限制：32MB

题目描述

小明发现和小宇有共同祖先！现在小明想知道小宇是他的长辈，晚辈，还是兄弟。

输入描述

输入包含多组测试数据。每组首先输入一个整数N（N<=10），接下来N行，每行输入两个整数a和b，表示a的父亲是b（1<=a,b<=20）。小明的编号为1，小宇的编号为2。 输入数据保证每个人只有一个父亲。

输出描述

对于每组输入，如果小宇是小明的晚辈，则输出“You are my younger”，如果小宇是小明的长辈，则输出“You are my elder”，如果是同辈则输出“You are my brother”。

输入示例

5
1 3
2 4
3 5
4 6
5 6
6
1 3
2 4
3 5
4 6
5 7
6 7

输出示例

You are my elder
You are my brother

解法一(模拟+哈希)

思路分析:

1. 由题意有小明与小宇有共同祖先,且每人只有一个父亲,所以小明与小宇处于一定处于一个关系图谱内;
2. 对于确认小宇与小明的关系,只需确认各自所处家族图谱的层级即可
3. 若小宇层级比小明低,则是晚辈;同级则是同辈;层级比小明高,则是长辈

实现代码如下:

public class k_11_CommonAncestor {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 记录组数
        int n;
        // 处理每组输入输出
        int a, b;
        while (in.hasNext()) {
            n = in.nextInt();
            int[] data = new int[22];
            // 读取每组数据
            while (n-- > 0) {
                data[in.nextInt()] = in.nextInt();
            }
            int highM = getHighLevel(data, 1);
            int highY = getHighLevel(data, 2);
            if (highY > highM) {
                // 说明小宇是小明的晚辈
                System.out.println("You are my younger");
            } else if (highY == highM) {
                // 说明小宇是小明的同辈
                System.out.println("You are my brother");
            } else {
                // 说明小宇是小明的长辈
                System.out.println("You are my elder");
            }
        }
    }
    // 输入编号 获取其长辈层级高度
    private static int getHighLevel(int[] data, int code) {
        int high = 0;
        while (data[code] != 0) {
            ++ high;
            code = data[code];
        }
        return high;
    }
}

运行结果如下:

运行时间： 418ms 消耗内存： 12956kb

复杂度分析:

• 时间复杂度: $O(n)$
• 空间复杂度: $O(1)$