这道题目非常easy,但是我还是要讲一下两种做法
第一种,也就是我最开始直接想到的,求出割点后缩成一颗树,然后再判断
第一种固然简单,但是第二种方法则是利用了割点判定法则的证明过程(即删掉一个点后,具体哪些子树会与上面一整坨失去连通性)
就是当前搜索到\(x\)的时候,我们会枚举一个子树根节点\(y\),若\(dfs[x]≤low[y]\),则说明\(x\)是割点,还说明删去\(x\)后,\(y\)这棵子树会直接成为一个单独的连通块,然后我们就只需要判断\(b\)在\(y\)的子树里面就可以了(最开始以\(a\)为搜索树的根)
标签:第一种,连通性,嗅探器,割点,搜索,一整 From: https://www.cnblogs.com/dingxingdi/p/18013337