PTA天梯赛L2-016题深度解析：用DFS实现家族关系高效判定

当算法竞赛遇到中国传统的"五服"制度，会碰撞出怎样的火花？这道PTA天梯赛L2-016题将家族关系判断与图遍历算法巧妙结合，成为检验选手实际问题建模能力的经典案例。作为竞赛选手，我们需要在理解传统文化规则的基础上，将其转化为计算机可执行的判定逻辑。

1. 问题本质与算法选择

题目要求判断两个人是否在五服之内（即是否存在五代以内的共同祖先），这本质上是一个家族关系图的连通性判断问题。我们需要考虑几个关键特征：

• 数据规模：最多10^4个人物节点，要求算法时间复杂度控制在O(N)级别
• 查询特性：需要频繁判断两个人的亲属关系（最多10^4次查询）
• 遍历深度：只需要考虑五代以内的亲属关系

**DFS（深度优先搜索）**成为最合适的选择，原因在于：

1. 实现简单直观，适合竞赛环境快速编码
2. 五代限制天然对应DFS的深度参数
3. 不需要完整遍历整个家族图，遇到深度限制即可返回

与BFS相比，DFS在这种特定深度限制的场景下更具优势。我们来看一个简单的亲属关系示例：

A ├── B │ ├── D │ └── E └── C ├── F └── G

当判断B和C的后代关系时，DFS会沿着每条分支深入，直到达到五代限制。

2. 数据结构设计与预处理

高效的数据结构是算法实现的基础。针对本题，我们需要设计能够快速查询以下信息的数据结构：

• 每个人的性别信息
• 每个人的父母信息
• 每个人的后代信息（反向索引）

2.1 核心数据结构实现

const int MAX_ID = 100000; // 题目说明ID为5位数 char gender[MAX_ID]; // 性别记录数组 vector<int> parents[MAX_ID]; // 父母关系图 set<int> ancestors[2]; // 两个人的五代祖先集合

关键预处理步骤：

1. 读取每个人物信息时，同时记录其父母的性别
2. 建立从子女到父母的关系指针
3. 特别注意处理父母信息缺失的情况（ID为-1）

注意：题目虽然保证输入数据中每人只有一个性别，但在实际处理时仍需考虑父母性别记录的完整性，这是许多选手容易忽略的边界条件。

3. DFS实现与优化技巧

标准的DFS实现需要针对本题特点进行优化。以下是竞赛中经过验证的高效实现方案：

3.1 基础DFS框架

void dfs(int current, int depth, int person_index) { if(depth > 5) return; ancestors[person_index].insert(current); for(int parent : parents[current]) { if(parent != -1) { dfs(parent, depth + 1, person_index); } } }

3.2 竞赛实用优化技巧

1. 提前终止：当发现共同祖先时立即返回，不必继续完整遍历
2. 双集合比对：先收集一个人的所有五代亲属，再检查另一个人的亲属是否存在于该集合
3. 性别优先判断：在DFS前先判断两人性别，同性可直接返回结果

优化后的查询逻辑：

bool canMarry(int a, int b) { if(gender[a] == gender[b]) return false; ancestors[0].clear(); ancestors[1].clear(); dfs(a, 1, 0); dfs(b, 1, 1); for(int relative : ancestors[1]) { if(ancestors[0].count(relative)) { return false; } } return true; }

4. 常见错误与调试技巧

在竞赛环境中，这道题有几个典型的"坑点"需要特别注意：

4.1 易错点列表

1. 父母性别记录遗漏：

   • 只记录了输入人物的性别而忽略了父母性别
   • 解决方案：在输入时显式设置父母性别

2. ID边界处理不当：

   • 未考虑ID为-1的情况直接访问数组导致越界
   • 解决方案：在访问前检查parent != -1

3. 五代计算错误：

   • 将"五代"理解为五层而非五代（本人为第一代）
   • 正确理解：本人(1)→父母(2)→祖父母(3)→曾祖父母(4)→高祖父母(5)

4. 集合未清空：

   • 多次查询间未清空祖先集合导致结果污染
   • 解决方案：每次查询前清空集合

4.2 调试技巧

当遇到WA（Wrong Answer）时，可以构造以下测试用例进行验证：

5. 完整竞赛级代码实现

结合上述所有优化和注意事项，以下是适合竞赛环境的高效实现：

#include <bits/stdc++.h> using namespace std; const int MAX_ID = 100000; char gender[MAX_ID]; vector<int> parents[MAX_ID]; set<int> ancestors[2]; void dfs(int u, int depth, int idx) { if(depth > 5 || u == -1) return; ancestors[idx].insert(u); for(int parent : parents[u]) { dfs(parent, depth + 1, idx); } } void solve() { int n, k; cin >> n; while(n--) { int id, father, mother; char g; cin >> id >> g >> father >> mother; gender[id] = g; if(father != -1) { gender[father] = 'M'; parents[id].push_back(father); } if(mother != -1) { gender[mother] = 'F'; parents[id].push_back(mother); } } cin >> k; while(k--) { int a, b; cin >> a >> b; if(gender[a] == gender[b]) { cout << "Never Mind" << endl; continue; } ancestors[0].clear(); ancestors[1].clear(); dfs(a, 1, 0); dfs(b, 1, 1); bool hasCommon = false; for(int rel : ancestors[1]) { if(ancestors[0].count(rel)) { hasCommon = true; break; } } cout << (hasCommon ? "No" : "Yes") << endl; } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); solve(); return 0; }

这段代码经过了PTA平台的实际验证，包含了所有必要的优化和边界处理。在竞赛环境中，建议使用更简洁的变量名以加快编码速度，但核心逻辑保持不变。

6. 算法扩展与变式思考

虽然DFS是本题的最直接解法，但我们可以进一步思考其他可能的解决方案和优化空间：

6.1 替代算法对比

6.2 性能优化方向

对于更大规模的数据，可以考虑以下优化：

1. 记忆化存储：缓存每个人的五代祖先集合
2. 双向搜索：同时从两个人出发向祖先搜索
3. 迭代式DFS：避免递归深度限制

7. 竞赛实战建议

在真实的竞赛环境中，处理这类题目时建议遵循以下步骤：

1. 仔细阅读题目：特别注意关于数据范围和特殊条件的说明
2. 设计数据结构：选择最适合题目要求的数据存储方式
3. 编写伪代码：先理清算法流程再着手编码
4. 处理边界条件：特别是输入中的-1等特殊值
5. 构造测试用例：包括极端情况和典型情况

这道L2-016题很好地展示了如何将传统文化规则转化为算法问题。掌握这种转换能力，是成为高水平竞赛选手的关键。在实际编码时，保持代码模块化和清晰的结构，有助于快速调试和修改。