当前位置：首页 > news >正文

PTA天梯赛L2-016题保姆级攻略：用DFS搞定‘五服禁婚’判断（附C++完整代码）

news 2026/5/6 7:11:29

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

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

1. 问题本质与算法选择

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

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

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

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

与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]; // 两个人的五代祖先集合

关键预处理步骤：

读取每个人物信息时，同时记录其父母的性别
建立从子女到父母的关系指针
特别注意处理父母信息缺失的情况（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 竞赛实用优化技巧

提前终止：当发现共同祖先时立即返回，不必继续完整遍历
双集合比对：先收集一个人的所有五代亲属，再检查另一个人的亲属是否存在于该集合
性别优先判断：在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 易错点列表

父母性别记录遗漏：
- 只记录了输入人物的性别而忽略了父母性别
- 解决方案：在输入时显式设置父母性别
ID边界处理不当：
- 未考虑ID为-1的情况直接访问数组导致越界
- 解决方案：在访问前检查parent != -1
五代计算错误：
- 将"五代"理解为五层而非五代（本人为第一代）
- 正确理解：本人(1)→父母(2)→祖父母(3)→曾祖父母(4)→高祖父母(5)
集合未清空：
- 多次查询间未清空祖先集合导致结果污染
- 解决方案：每次查询前清空集合

4.2 调试技巧

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

测试案例	预期结果	检查重点
同性查询	Never Mind	性别判断逻辑
直系血亲	No	父母关系处理
远房表亲	Yes	五代边界判断
父母信息缺失	根据情况	-1处理逻辑

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 替代算法对比

算法	优点	缺点	适用场景
DFS	实现简单，深度控制自然	重复计算多	查询次数少时
BFS	层次遍历直观	需要额外记录层数	需要广度优先时
并查集	查询速度快	难以处理五代限制	不适用本题
预处理所有关系	查询O(1)	预处理开销大	查询极多时