一句话理解
缩点 DAG 上做最长路、方案数。
为什么要学
有向图带环先缩。
讲解
入度 0 的块开始拓扑 DP。
例子
先把环处理掉。
常见错误
- 不缩点在环上 DP。
- 重边没去。
第 445 课
缩点 DAG
🔴 提高 约 12 分钟
练习 做完再看下一课
有环有向图求最长路，常先？
进度保存在本机浏览器里。
左右方向键也可翻课
第 445 课
缩点 DAG 上做最长路、方案数。
有向图带环先缩。
入度 0 的块开始拓扑 DP。
先把环处理掉。
有环有向图求最长路，常先？
左右方向键也可翻课