如何在DAG中高效查找多源直接子节点？

问题定义 #

给定有向无环图（DAG）和源节点集合 ( S = {S_1, S_2, ..., S_n} )：

• 有效节点：能被所有源节点到达的节点（即对于任意 ( S_i \in S )，存在从 ( S_i ) 到该节点的路径）。
• 多源直接子节点：属于有效节点，且其所有父节点（原DAG中的前驱节点）都不是有效节点的节点。

高效算法（O(V+E)时间复杂度） #

可以通过以下三步实现，整体时间复杂度为 ( O(V+E) )：

1. 统计每个节点被多少个源节点可达

• 初始化数组 cnt[]，所有元素设为0；对于每个源节点 ( s \in S )，设置 cnt[s] = 1。
• 对原DAG执行拓扑排序（DAG的拓扑排序可在 ( O(V+E) ) 时间完成）。
• 按照拓扑序依次处理每个节点 ( u )：
  • 对于 ( u ) 的每个邻居 ( v )（即原DAG中存在边 ( u \rightarrow v )），将 cnt[v] += cnt[u]。
• 核心逻辑：拓扑序保证处理 ( u ) 时，所有能到达 ( u ) 的路径已被处理完毕，cnt[u] 即为能到达 ( u ) 的源节点总数。

2. 确定有效节点集合

遍历所有节点，将满足 cnt[u] = |S| 的节点标记为有效节点（这类节点能被所有源节点到达）。

3. 筛选多源直接子节点

• 初始化数组 has_valid_parent[]，所有元素设为 false。
• 遍历原DAG的所有边 ( u \rightarrow v )：
  • 如果 ( u ) 是有效节点，则将 has_valid_parent[v] = true（表示 ( v ) 有一个有效父节点）。
• 最后遍历所有有效节点，收集所有 has_valid_parent[u] = false 的节点，这些就是所求的多源直接子节点。

算法正确性验证 #

以题目示例为例：

• 源节点 ( S_1, S_2, S_3 ) 的 cnt 值均为1，不等于 ( |S|=3 )，因此不属于有效节点。
• 节点 ( a, b, c ) 的 cnt 值均为3，属于有效节点。
• 遍历边时，若 ( c ) 的父节点是有效节点，则 has_valid_parent[c] = true，而 ( a, b ) 的父节点都是源节点（非有效节点），因此 has_valid_parent[a] 和 has_valid_parent[b] 保持 false，最终结果为 ( a, b )，与示例一致。

对比朴素算法的优势 #

朴素算法因需要为每个源节点单独计算可达集，时间复杂度为 ( O((V+E)*S) )；而上述算法通过拓扑排序一次性统计所有源节点的可达情况，再通过一次遍历筛选结果，整体时间复杂度降至 ( O(V+E) )，在源节点数量较多时效率提升显著。

内容的提问来源于stack exchange，提问作者Pragy Agarwal