Flipkart笔试题：从广告对生成字典序最小的广告播放序列

你的思路完全正确，这本质是有向图的遍历问题，核心目标是从指定起点出发，找到一条覆盖所有节点（广告）的路径，且序列字典序最小。

问题建模 #

把每个广告视为图的节点，每个广告对(X, Y)对应一条有向边X → Y。问题转化为：

• 从起点"ABC"出发，寻找包含所有节点的路径（允许重复经过节点，但所有节点至少出现一次）；
• 若存在多条可行路径，选择字典序最小的那条。

核心解法：贪心+DFS #

要构造字典序最小的序列，关键是每一步优先选择字典序最小的后继节点，同时保证后续能遍历完所有剩余节点。具体步骤：

1. 构建有序邻接表：用邻接表存储每个节点的所有后继，并对每个节点的后继列表按字典序升序排序——这样每次优先遍历最小的候选节点。
2. 预计算可达性：对每个节点，用DFS或BFS预处理出从该节点能到达的所有节点集合。这一步是为了避免贪心选了小字典序节点后，无法覆盖剩余未访问的节点。
3. 贪心DFS遍历：从起点出发，按字典序遍历当前节点的后继：
   • 若候选节点未被访问，或访问后仍能到达所有未遍历的节点，则选择该节点加入序列，递归处理；
   • 一旦找到覆盖所有节点的路径，直接返回——因为按字典序优先选择的第一个可行路径就是最小的。

示例验证 #

示例中的图是一条线性链：ABC → TUV → QWE → XYZ → IOP，每个节点只有唯一后继，所以直接按顺序遍历就是唯一可行路径，自然也是字典序最小的。

特殊情况处理 #

• 若从起点出发无法到达所有节点，则不存在满足条件的序列；
• 若节点有多个后继分支，必须通过可达性检查确保选小字典序节点后，剩余节点仍能被遍历，避免陷入死胡同。

内容的提问来源于stack exchange，提问作者Sleepy Tinker