高度由习惯堆积

分类 算法:Tarjan 下的文章

BZOJ2574 Store-Keeper

题目题目地址思路仔细分析一下会发现,其实此题的状态数并不多,只有$100*100*4$种,人的移动是不需要的,也就是说,我们只需要知道当箱子在某一个位置时,人能不能从箱子的一个侧面走向另一个侧面。转化成图论模型也就是说,当一个无向图断掉一个点之后,判断两个点的连通性。这就让人想到了COCI2006/2007 Final的题,这是那道题的一个子问题。首先用$Tarjan$将$dfs$树建立出来...
February 17, 2019

tarjan求强联通分量

title: tarjan求强联通分量date: 2018-08-30 13:26:53tags: 模板集合tarjan算法简介强连通分量(英语:Strongly connected component)是图论中的概念。图论中,强连通图指每一个顶点皆可以经由该图上的边抵达其他的每一个点的有向图。意即对于此图上每一个点对(Va,Vb),皆存在路径Va→Vb以及Vb→Va。强连通分量则是指一张有...