求SCC后缩点重新构图,就是个DAG
每对顶点间单连通则必存在一条链经过所有的顶点
首先入度为0的点必为1个(存在多个不构成链,是DAG,不可能不存在)
开始的想法是根据出度数+去重边直接判定...后来发现有点bug,不一定是树
比如
3 3
1 2
1 3
3 2

比较暴力就是从入度0的点开始DFS遍历所有路线,记录最大深度

之后想到用拓扑排序,每次从栈中取出顶点u,压入栈的u的邻点必定只有一个

但是时间还是一样,应该是求SCC花的时间占的多,对于随机数据缩点后的图点数,边数应该都会减少.