Java教程

2022.2.21蓝桥杯准备训练

本文主要是介绍2022.2.21蓝桥杯准备训练,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

时隔多年,再次入坑算法竞赛。。。。。
今天复习了点双,边双,割边缩点,割点缩点,强联通分量。
在强联通分量板题中,注意tarjan中的写法

if(!dfn[t]){
           tarjan(t);
           low[x] = min(low[x],low[t]);
       }else if(ins[t]){
           low[x] = min(low[x],dfn[t]);
       }

而不是

if(!dfn[t]){
            dfs(t);
            low[x] = min(low[x],low[t]);
        }else {
            low[x] = min(low[x],dfn[t]);
        }

这里和无向图的点双边双不同,务必保证树边连下去的点不在其他的连通分量中时,才做更新low的操作

这篇关于2022.2.21蓝桥杯准备训练的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!