缩点入门
缩点入门
缩点,经典图论算法,用来将有环图缩成无环图(DAG),为DP做准备
前置技能:存图,dfs
先掌握一些定义:
强连通图:任意两点间均可达的图
强连通分量:一个图中任意两点间均可达的子图
所以,要缩点,就是用一些点来表示一个图中的所有强连通分量
常用Tarjan算法对有向图缩点
Tarjan算法用dfs实现(所以有一棵"搜索树"),并用栈维护从根节点到当前节点的路径
再掌握一些定义:
树枝边:指向未访问过的节点的边
后向边:指向栈中节点的边
前向边:指向已访问过且是当前节点的子孙的边
横叉边:指向已访问过且不是当前节点的子孙的边
有一张图: