RT,现有两篇题解感觉都在口胡,完全看不懂。
去看了 CF 官方题解,完全不知道它的 Processing an edge (u,v) 说的是原图的边还是构造的新图的边。如果是原图的边那就和 k 没关系了,如果是新图的边又不知道是怎么把新图的 DAG 转化成原图的 DAG 的。
或者,有人能帮忙证明下面这个东西吗?
有 2 个有向图 G 和 G′,保证 G 中的一条边 u→v 在 G′ 中满足 u 可以到达 v。可不可以证明 G 中的最大点导出 DAG 比 G′ 中的最大点导出 DAG 大或者相等?