首页 > 代码库 > 小结:双连通分量 & 强连通分量 & 割点 & 割边
小结:双连通分量 & 强连通分量 & 割点 & 割边
概要:
各种dfs时间戳。。全是tarjan(或加上他的小伙伴)无限膜拜tarjan orzzzzzzzzz
技巧及注意:
强连通分量是有向图,双连通分量是无向图。
强连通分量找环时的决策和双连通的决策十分相似,但不完全相同。
强连通分量在if(FF[v])后边的else if还要特判是否在栈里,即vis[v],然后才更新LL[u]
割点和强连通分量因为是无向图所以要判个fa,可以在dfs时维护个fa参数
割点如果要求分割的分量,那么就是这个节点对他的子树是割点的数目+1。
割点不需要栈维护但是要在后边判当前节点是否为root(即child==1且为root时,这个点就不是割点),而双连通分量不需要特判根节点,而需要在LL[v]>=FF[u]那里直接维护bcc即可。
割边的话其实就是割边的特例即可,即LL[u]>FF[u]就行了。。
边-双连通分量的话比点的好做,就是求出割边后所有不经过割边的环就都是了,dfs之。
割点例题:【POJ】1523 SPF(割点)(注意特判root)
双连通分量例题:【POJ】2942 Knights of the Round Table(双连通分量)(注意不要忘记栈是在两个if内添加的)
小结:双连通分量 & 强连通分量 & 割点 & 割边
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。