高效判定是否存在有向无环图（DAG）的算法设计问询

给定一组图节点用于构建有向图，每个图节点的边集由树结构定义：从树的根节点遍历到叶子节点时，将路径上所有树节点的边集取并集，得到该节点的一组有效边；图节点的可选边集总数等于对应树的叶子节点数量。

需要设计优先降低时间复杂度、其次优化空间复杂度的高效算法，完成两个目标：

• 判断是否能通过选择每个节点的某一组边集，构建出有向无环图（DAG）；
• 若无法构建，报告导致无法破除环的图节点集合。

已知基础 #

已掌握针对「每个节点仅含一组边」场景的环检测算法与强连通分量分析方法，但不清楚如何处理「每个节点多组可选边集」的情况。

示例说明 #

示例1：无法构建DAG #

{ A } // 节点定义
-> // 指向邻居的边集树
[] // 树结构
[A], [B] // 生成的两组可选边集

{ B }
->
[A] // 仅一组可选边集

此场景无法构建无环图：节点B必须指向A，而A的两组可选边集（指向自身/指向B）都会形成环，因此问题节点为A。

示例2：可构建DAG #

{ A }
->
[]
[A], [] // 两组可选边集：指向自身 / 无指向

{ B }
->
[]
[A], [B] // 两组可选边集：指向A / 指向自身

此场景可构建无环图：选择A的「无指向」边集、B的「指向A」边集，即可得到合法DAG。

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