『素瘤算法系列10』魔法石(tarjan·边双连通分量)

本文主要是介绍『素瘤算法系列10』魔法石(tarjan·边双连通分量)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

$\mathrm{P}\mathrm{r}\mathrm{o}\mathrm{b}\mathrm{l}\mathrm{e}\mathrm{m}$

幻象群岛是由$n$个孤立的岛屿构成。岛屿之间有一些残破的石桥，而桥心的石墩上，就有可能镶嵌着上古魔法石。约翰尼可以通过这些石桥，从一座岛跑到另一座岛，如果岛上恰好有魔法石，他就可以顺便收集。但是由于这些石桥实在是太残破了，约翰尼经过之后，石桥就会崩塌，不能再次通过。（由于约翰尼踩过的部分很快就会崩塌，所以他也不能先跑到桥心，然后原路返回）。

约翰尼现在处在岛a，而岛b上则有一个传送门，只有在那里，约翰尼才能安全地离开幻象群岛。约翰尼想知道，他能顺利地收集到至少一块上古魔法石，并安全离开吗？

$\mathrm{S}\mathrm{o}\mathrm{l}\mathrm{u}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}$

前置芝士：

• 边双连通分量：该分量内任意两点都存在两条边不想交的路径。
• 点双连通分量：该分量内任意两点都存在两条点不相交的路径。

我们知道边双的求法可以直接使用割边来分割，即如果一条边是割边，那么它一定不属于任意一个边双内；而且，一个边双内也不存在割边。

回归本题：
联系变双，求$s$到$t$是否存在一条路径，使得一条边的边权为$1$，可以转化为：

• 添加边$(s,t,0)$的情况下是否存在两条从$s$到$t$的两条不相交的路径。
• 相当于问你$s$和$t$

这篇关于『素瘤算法系列10』魔法石(tarjan·边双连通分量)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---