无信息损失地将有向图转化为DAG的方法探究

你正在尝试寻找绕开强连通分量（SCC）分解的简便方法，将有向图转化为无环图且不损失信息——这个方向确实很有价值，毕竟Tarjan或Kosaraju这类SCC算法在处理大规模图时，时间与空间开销都不算低，能找到更轻量的替代思路会非常实用。

你提到的“对于一个po...”看起来没写完，不过我可以先分享几个无需全局SCC计算的可行思路，说不定能和你的想法契合：

• 增量式边拆分去环：遍历图中的每条边，若检测到该边会形成环（即从终点可回溯至起点），则将这条边拆分为两条边并引入一个虚拟节点。比如原边u→v形成环时，拆为u→x和x→v，同时给虚拟节点x附加原边的完整信息。这种方法无需全局遍历找SCC，边处理边保证子图无环，且原始边的信息完全通过虚拟节点保留。
• 拓扑排序导向的边标记调整：先尝试对图执行拓扑排序，遇到无法完成排序的节点组（即存在环的节点集合），不直接合并成SCC，而是选择环中的一条边进行“带标记的重定向”。比如环a→b→c→a中，将c→a改为c→a'，其中a'是a的镜像节点，同时记录a'与a的等价映射关系。调整后图成为DAG，且通过镜像节点的映射可完整还原原始图的连通性。
• 基于可达性判断的节点映射：先计算每个节点到其他节点的可达性，将互相可达的节点标记为等价组，但不合并成单个节点，而是为每个等价组设置一个代表节点，其余节点作为“影子节点”保留，影子节点到代表节点的边标记为“自环映射”。这种方法无需显式识别SCC，通过可达性判断构建DAG，原始节点的所有信息都在影子节点中得以保留。

需要注意的是，“不损失信息”需要明确界定：是要保留所有路径的细节信息，还是仅保留节点间的可达性关系？不同的定义会影响方案的设计方向。如果你能补充完整未写完的思路（比如是不是基于partial order（偏序）的想法？），我可以帮你进一步细化验证可行性。

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