用C++手把手教你搞定PTA L2-030冰岛人：从建树到五代内公共祖先判断（附完整代码）

冰岛人的家族关系判断问题看似简单，实则暗藏多个算法陷阱。这道PTA L2-030题目要求我们处理复杂的家族树结构，并实现五代内公共祖先的快速判断。作为一道25分的模拟题，它不仅考察数据结构的选择能力，更考验对边界条件的处理和对性能优化的敏感度。

在实际解题过程中，很多同学会遇到TLE（时间限制超出）和WA（错误答案）的困扰。本文将带你从零开始构建解决方案，重点解析如何避免常见错误，并最终提交一份高效通过的代码。我们会采用 map 存储家族关系，优化双重循环的判断逻辑，并特别关注输入输出的性能瓶颈。

1. 数据结构设计与输入处理

1.1 家族关系的存储方案

面对这类家族关系问题，首要任务是选择合适的数据结构。我们需要快速查询任意一个人的性别及其父亲信息，因此哈希表（ unordered_map ）是理想选择：

struct Person {
    char gender;
    string father;
};
unordered_map<string, Person> family;

这种设计将每个人的名字作为键，性别和父亲名作为值存储。相比二叉树或链表，哈希表的查询时间复杂度为O(1)，能极大提升后续判断效率。

1.2 输入数据的解析技巧

题目输入包含两类数据：人口信息和查询请求。处理输入时有几个关键点需要注意：

1. 性别判断逻辑 ：
   • 维京后裔：姓以"sson"结尾为男性，"sdottir"结尾为女性
   • 其他人：姓以'm'或'f'结尾表示性别

for (int i = 0; i < n; ++i) {
    string name, surname;
    cin >> name >> surname;
    
    if (surname.back() == 'n') {  // 维京男性
        family[name] = {'m', surname.substr(0, surname.size() - 4)};
    } else if (surname.back() == 'r') {  // 维京女性
        family[name] = {'f', surname.substr(0, surname.size() - 7)};
    } else {  // 非维京人
        family[name].gender = surname.back();
    }
}

2. 输入性能优化 ： 当处理大规模数据（N≤10^5）时，标准输入输出可能成为性能瓶颈。添加以下优化：

ios::sync_with_stdio(false);
cin.tie(nullptr);

2. 五代内公共祖先判断算法

2.1 基础思路与常见错误

判断两人五代内是否有公共祖先的基本思路是：分别追溯两人的祖先链，检查在五代内是否有交集。但直接实现时容易出现两个问题：

1. TLE（时间超出限制） ：未优化双重循环导致时间复杂度爆炸
2. WA（错误答案） ：对"五代内"的理解有偏差，边界条件处理不当

原始代码中的问题示例：

if (i >= 5 && j >= 5) return 1;  // 过早终止导致错误
if (A == B && (i < 5 || j < 5)) return 0;  // 逻辑不严谨

2.2 优化后的判断逻辑

正确的判断应该满足：

• 只要两人在任意一方的五代内（包括第五代）有公共祖先，就返回false
• 只有当两人的所有公共祖先都超出五代时，才返回true

优化后的判断函数：

bool hasCommonAncestor(const string &a, const string &b) {
    unordered_set<string> ancestorsOfA;
    string current = a;
    
    // 记录a的五代内祖先
    for (int gen = 1; gen <= 5 && !current.empty(); ++gen) {
        ancestorsOfA.insert(current);
        current = family[current].father;
    }
    
    // 检查b的五代内祖先是否在a的祖先集合中
    current = b;
    for (int gen = 1; gen <= 5 && !current.empty(); ++gen) {
        if (ancestorsOfA.count(current)) {
            return true;
        }
        current = family[current].father;
    }
    
    return false;
}

这种方法将时间复杂度从O(N^2)降到了O(N)，有效避免了TLE问题。

3. 完整代码实现与关键优化

3.1 整体代码结构

#include <iostream>
#include <unordered_map>
#include <unordered_set>
using namespace std;

struct Person {
    char gender;
    string father;
};

unordered_map<string, Person> family;

bool hasCommonAncestor(const string &a, const string &b) {
    // 实现见上文
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    // 人口信息输入处理
    // 实现见上文
    
    int m;
    cin >> m;
    
    while (m--) {
        string name1, surname1, name2, surname2;
        cin >> name1 >> surname1 >> name2 >> surname2;
        
        if (!family.count(name1) || !family.count(name2)) {
            cout << "NA\n";
        } else if (family[name1].gender == family[name2].gender) {
            cout << "Whatever\n";
        } else {
            cout << (hasCommonAncestor(name1, name2) ? "No\n" : "Yes\n");
        }
    }
    
    return 0;
}

3.2 关键优化点解析

1. 输入输出加速 ：

   • ios::sync_with_stdio(false) 解除C++与C的IO同步
   • cin.tie(nullptr) 解除cin与cout的绑定

2. 数据结构选择 ：

   • 使用 unordered_map 替代 map ，查询时间从O(logN)降到O(1)
   • 在祖先判断中使用 unordered_set 快速查找

3. 算法优化 ：

   • 将双重循环改为单次预处理+单次查询
   • 严格限制追溯代数为5代，避免无限循环

4. 测试用例分析与调试技巧

4.1 常见WA原因与解决方法

错误类型	典型表现	解决方法
WA3	五代边界判断错误	确保i<5和j<5的判断逻辑正确
WA6	同名不同代处理不当	增加对两人是同名的特殊处理
TLE6	输入输出或算法效率问题	添加IO优化，改进算法复杂度

4.2 调试建议

1. 小规模测试 ：先用样例数据验证基本逻辑
2. 边界测试 ：
   • 测试两人为同一人的情况
   • 测试五代刚好是公共祖先的情况
   • 测试一人不在名单中的情况
3. 性能测试 ：
   • 生成最大规模数据（N=1e5）测试运行时间
   • 使用 chrono 库测量关键函数执行时间

#include <chrono>
auto start = chrono::high_resolution_clock::now();
// 测试代码
auto end = chrono::high_resolution_clock::now();
auto duration = chrono::duration_cast<chrono::milliseconds>(end - start);
cout << "Time: " << duration.count() << "ms\n";

在实际编程竞赛中，这类家族关系问题非常常见。掌握高效的数据结构选择和算法优化技巧，不仅能解决这道题目，也能为类似问题提供解题思路。代码中的IO优化技巧尤其值得注意，它们往往能决定程序是否能通过大规模数据的测试。