BZOJ1023/SHOI2008/cactus仙人掌图

Posted on By 二价氢

#题目描述

给一个缩环后变成树的简单无向图(仙人掌图),求其直径

#做法

首先,Tarjan,遇到环就环上DP缩环,DFS找到可能的直径,更新答案

#复杂度分析

时间复杂度为,其中N代表所有点数

#AC Code

AC Code