UVa 765 References光看题名我第一反应是——这题十有八九是让我处理参考文献条目要么比格式、要么做字符串截取。等真正读完题面才发现完全不是那么回事它给出一堆某ID references 某ID的关系要你输出每个ID最终引用到的全部ID。说白了这是一道套着引用外衣的有向图传递闭包题而且因为数据范围非常小实现难度不高真正容易翻车的全在理解题意和输出格式上。这篇文章我想把从读题、建图、写代码到被UVa老题输出格式坑了一遍的整个过程完整复盘一遍顺带聊聊这类依赖关系传递问题的通用解法。1. 题面拆解References到底要你算什么东西1.1 引用在这里不是文献是依赖题面给的是很朴素的关系描述A references B翻译成人话就是A 引用了 B。如果你把它理解成论文里的参考文献互相引用方向容易搞反——引用别人意味着你依赖别人。在这个抽象模型里A references B 等价于 A 指向 BA 通往 B 有一条有向边。关键在第二层引用是传递的。如果 A references BB references C那么 A 间接引用了 C。题目要的不是单纯罗列直接引用而是把每个 ID 出发、沿着有向边能走到的所有 ID 全部找出来。这个行为在离散数学里的名字叫做传递闭包英文是 transitive closure。看到传递闭包这个词基本就能确定这题不是字符串处理而是图论。这里插一句个人体会UVa 早期题目很喜欢用生活化词汇包装图论问题比如引用依赖连接剥开看都是同一套东西。所以做题第一步永远是翻译题面而不是急着写代码。1.2 数据范围决定了你可以用多暴力的招这类老题的输入规模通常很小。设节点数为 N最多也就几十比如 ID 由字母组成的话大写 26 个、小写 26 个一共 52 个边数 M 大概几百量级。小数据意味着你不需要上什么高级算法重点是建模正确、输出格式正确。不要一上来就想 Tarjan 缩点、再想 Floyd 加优化N≤52 的时候暴力 DFS 从每个节点跑一遍是完全可行的。复杂度 O(N(NM))最多也就 52 × 几百任何机器都是瞬间完成。当然如果题面没有明确说 ID 是单个字母而是任意长度的字符串那计算模型就要换一下用 map 或 unordered_map 做字符串到数字的映射把名字离散化之后再建图。我在做类似题时习惯先写一个 id() 函数统一分配编号后面所有代码都只跟 int 打交道这样逻辑会干净很多。1.3 直接建图之前先确认三个问题动手建图前我会先问自己三个问题边是有向还是无向references 明显是有向A 引用 B 不等于 B 引用 A。一个 ID 可以引用多个 ID 吗可以每条关系是独立的边。输出要不要包含自己通常不包含因为自己引用自己在正常定义下没有意义。这三个问题决定了静态数组开多大、DFS 里要不要跳过起点。别看问题小我见过不少人在第二个问题上栽跟头——把同一行里的多个引用当成一个字符串来处理结果图建得乱七八糟。还有一个细节值得留意输入里可能出现同一对关系重复多次也可能出现 A references A 这种自环稍后我会单独讲这两个边界。2. 建模与算法选型为什么我最终选了DFS加visited2.1 邻接表还是邻接矩阵小图不必纠结N≤52 的情况下两种存图方式都很舒服。邻接矩阵是 bool g[55][55]写起来最直观查边 O(1)邻接表是 vector g[55]遍历出边快但代码稍长一点。我当时的做法是邻接矩阵原因是传递闭包问题视觉上就是一个二维可达矩阵矩阵形式方便查错而且 N 这么小空间占用量连 1KB 都不到。如果 N 到几千邻接矩阵就不能这么用了那是另一个故事。但对 References 这种题直接矩阵就好不用提前优化。2.2 方案一Warshall 传递闭包三行代码解决一切学离散数学或者算法课的时候一定见过 Warshall 算法for (int k 0; k n; k) for (int i 0; i n; i) if (g[i][k]) for (int j 0; j n; j) g[i][j] g[i][j] || g[k][j];三层循环 O(N^3)N52 时大约 14 万次位运算几乎没有任何压力。优点代码极短、逻辑统一、天然处理了传递性。缺点如果需要输出从某个点出发可达的节点列表你还得再扫描一遍矩阵而且它把整张可达矩阵都算出来了而我们其实只需要每行的非零列。如果你喜欢这种全局视角用它完全没问题。但我在正式提交时没用它原因后面说。2.3 方案二带visited的DFS从每个点单独跑一遍思路非常直接对每个起点 s做一次 DFS凡是能从 s 走到的节点都标记进集合最后把集合里不等于 s 的节点按顺序输出。为了防止循环引用导致死循环需要一个 visited 数组每个起点重置一次void dfs(int u, vectorint reach) { for (int v : adj[u]) { if (vis[v]) continue; vis[v] true; reach.push_back(v); dfs(v, reach); } }这里的关键是visited 防止重复访问同时也保证了在环上不会无限绕圈。visited 标记的是本趟 DFS 是否来过而不是全局是否访问过所以每换一个起点都要清空。用 BFS 也可以效果完全一样。DFS 写起来更短递归的栈深度在 N≤52 时也完全不用担心。2.4 为什么我最终选DFS而不是Warshall讲道理这个数据规模 Warshall 完全能过。我选 DFS 主要有两个实际考量。第一输出格式要求每个 ID 后面跟它的引用列表这个列表需要按 ID 的字典序输出还是按输入顺序输出如果用 Warshall 算出全局可达矩阵我仍然需要遍历每一行、筛出非零列、再排序本质上并不比 DFS 省事。第二DFS 的过程天然对应从某个起点延伸出去的思维模型调试时可以用很简单的 print 语句逐步看出错了容易定位。Warshall 出问题往往是整体性错误对新手不太友好。从工程角度说两者对这道题都是足够快的正确解法选哪个都可以。我的建议是如果你正在学习图论两种都写一遍你会更深刻地理解什么叫传递闭包如果只是想把题过了选你最有把握的那个。3. 完整实现与输出格式化UVa老题最爱的隐藏坑3.1 核心代码框架我给出一个能直接跑通思路的 C 框架。这里我按最常见的输入格式来拆解每行是一条 A references B 形式的关系ID 先映射成整数再建图。#include bits/stdc.h using namespace std; const int MAXN 60; vectorint adj[MAXN]; bool vis[MAXN]; mapstring, int id; vectorstring name; int getId(const string s) { if (id.count(s)) return id[s]; int cur name.size(); id[s] cur; name.push_back(s); return cur; } void dfs(int u, vectorint reach) { for (int v : adj[u]) { if (vis[v]) continue; vis[v] true; reach.push_back(v); dfs(v, reach); } } int main() { string a, tmp, b; while (cin a tmp b) { int u getId(a); int v getId(b); adj[u].push_back(v); } int n name.size(); for (int s 0; s n; s) { memset(vis, 0, sizeof(vis)); vis[s] true; // 起点不参与自己的 reach vectorint reach; dfs(s, reach); sort(reach.begin(), reach.end()); cout name[s] :; for (int i 0; i (int)reach.size(); i) { cout name[reach[i]]; } cout \n; } return 0; }注意vis[s] true这一行把起点先标记成已访问就不会把 s 自己加进 reach。如果你忘了这一句在存在环的情况下DFS 绕一圈回到起点reach 里就会出现自己引用自己这种非法项。3.2 输出空列表的表示最容易翻车UVa 老题的输出格式要求往往精确到多一个空格都 Wrong Answer。References 这类题通常是这样每个 ID 占一行先输出 ID再输出冒号冒号后面跟着它能引用到的所有 ID用空格分隔如果它没有任何可达节点冒号后面直接换行不留空格。我当年第一次交就是栽在空列表后面多打了一个空格上。你看着没什么判题机不会给你解释。正确写法是先判断 reach 是否为空为空就直接输出Name:加换行非空再进入循环在每两个 ID 之间加分隔空格这样首尾都不会有多余空格。这种格式问题看起来蠢但在真实比赛中会消耗大量时间。我现在的习惯是上机前先手写一个完整样例的预期输出逐字节对照包括行尾空格和空行。3.3 手推一遍样例验证逻辑假设输入三条关系A references BB references CA references C建图是 A→BB→CA→C。以 A 为起点 DFS从 A 走到 B把 B 加入 reach从 B 走到 C把 C 加入 reach然后回到 A 的另一个出边 A→CC 已经被访问过跳过。于是 A 的引用列表是 {B, C}。B 作为起点时B→Creach 是 {C}。C 没有出边reach 为空输出C:空列表。这个例子很简单但它验证了三个要素直接引用、间接引用、去重A→C 这条直接边和 A→B→C 这条间接路径在结果中只出现一次。我的习惯是拿这种最小样例先在草稿纸上跑一遍再对照代码输出基本能把 80% 的建模错误提前扼杀掉。4. 循环引用、重复边和自环实测中踩到的三个边界4.1 循环引用会让朴素DFS死循环吗如果 A references B、B references A从 A 出发DFS 会走 A→B→A→B……如果没有 visited 数组递归栈直接爆掉。加了 visited 之后起点 Avis[A] true。走到 Bvis[B] true把 B 加入 reach。B 的出边是 A但 vis[A] 已经为 true直接跳过。这一趟正常结束reach {B}。所以循环引用不可怕可怕的是忘了防环。这里有一个容易忽略的点如果你把 visited 定义成全局 bool 数组一定要在每次新起点前 memset 清零一次否则第二个起点会沿用上一趟的访问痕迹结果凭空少一堆节点。这种 bug 非常阴间因为运行结果看起来有点合理不仔细对样例根本发现不了。4.2 重复引用要不要去重输入里可能出现两次 A references B也可能存在 A→B 直接边和 A→C→B 间接路径同时存在的情况。DFS 的 visited 机制天然会去重——同一个 v 只会被 push 进 reach 一次。所以只要 visited 逻辑正确你最终集合里不会出现重复节点。如果你选择了先把所有可达点存进 set 再统一输出的方案去重也是自动的。但如果用真·朴素 DFS不加 visited重复边会直接导致同一个点被 push 多次最终输出多出一堆重复项。所以去重不是额外工作而是 visited 机制的红利。4.3 自环A references A 算什么按常识一个 ID 不能引用自己但输入数据不一定讲武德。我倾向于把自环当成普通边但处理时让它不影响结果。做法就是我在 3.1 里写的DFS 前把 vis[s] 设为 true这样任何能绕回起点的路径都不会再把 s push 进 reach。如果自环出现在非起点的节点上也无所谓DFS 走到 u 时u 的自环指向 u但 vis[u] 已经为 true直接跳过。你可能会问如果把自环算进引用列表会怎样输出里会出现 A: A ...在逻辑上大概率不符题意。所以不管题面有没有明说我都会按不含自己处理并且在本地测试时专门构造一个带自环的用例验证。5. 从References延伸这类依赖传递题的通用套路5.1 传递闭包的三种打开方式References 只是依赖传递问题的入门款同族还有大量题目比如构建系统的依赖检查、包管理器依赖分析、课程先修关系判断。它们的核心都是给定有向图求可达关系。常用的有三个工具Warshall 算法O(N^3)适合 N≤500 且要全矩阵的场景每个点跑 DFS/BFSO(N(NM))适合稀疏图、需要按起点输出列表的场景Floyd-Warshall 最短路变种如果要算的是最短路径长度而不是是否可达就升级成带权的 Floyd。哪种最好取决于你要什么。References 要的是每个起点输出列表DFS 方案最顺手。如果题目问有多少对点互相可达Warshall 一次算完更方便。5.2 变式一反向引用统计被谁引用如果把边反过来A references B 改成B 被 A 引用就可以统计每个节点的入度来源。这在依赖注入、构建系统里很常见——想知道改了一个模块会影响哪些上层模块就要反向建图跑 DFS。代码几乎不用改只是建图时把边的方向反过来。我在实际项目中确实遇到过类似需求某个配置项变更后要找出所有会受影响的模块。把依赖看成引用和 References 里 A references B 的模型一模一样只是当年在刷题后来在写工程。这也是为什么我一直建议别小看 UVa 老题它们训练的是底层的建模能力。5.3 变式二检测环并列出环内成员如果题目升级成找出所有包含在循环引用里的 ID那就不是传递闭包能直接搞定的要上拓扑排序。拓扑排序能删掉所有不在环上的节点剩下的要么是环要么是环上的挂件。想列出环成员的话再用剩下的节点做一次 DFS 收集即可。这也是 References 之后值得练习的进阶路线。具体做法是先统计每个节点的入度把入度为 0 的节点不断删掉并把相邻节点的入度减一。剩下的节点就是所有互相引用的候选。这个过程在工程里很有用比如配置文件互相 include 导致死循环时用拓扑排序能快速定位是哪些文件在绕圈。5.4 我现在的做题习惯踩过输出格式的坑、吃过没清 visited 的亏之后我总结了一套自己的流程也分享给你先根据题面写一个最小样例把预期输出逐字节写出来再决定算法数据规模允许时优先选思路最简单、错了最好查的方案编码时把所有边界自环、重复边、空列表写进注释提醒自己提交前跑一遍自造的环和重复边用例最后检查输出行尾空格和空行。这套流程尤其适合 UVa 老题——它们数据不大不考炫技考的就是你能不能把每一步想清楚、把格式做干净。References 就是这样一道看着像字符串题其实是图论题的典型把它彻底弄懂后续再遇到依赖传递类问题你会觉得所有题都长得差不多至少我自己是这样。