洛谷 P5058 [ZJOI2004]嗅探器（割点）

1、 图中，找到一个割点 u， 把 a和b点，分割在不同的连通块
2、 从点a 开始深搜， dfn[i] 记录点i的访问顺序。
3、 对于一个割点 u ，若判定 u 为割点的边是 (u,v),那么有以下讨论,
链接: 看洛谷题解
如果 dfn[b] < dfn[u]，则 b 是 u 的祖先或者 b 和 u 不在同一个子树内，
由于 a 是根，那么 a和 b 一定在一个连通块内。

如果 dfn[b] > dfn[u] and dfn[b] 则 b 是 v 的兄弟子树中的节点，无法确定 a,b 是否在一个连通块。

如果 dfn[b] >= dfn[v]，则 b 是 v 的子树中的节点，a,b
一定不在一个连通块。

大概这三种情况就对应上述三种图

综上满足dfn[b] >= dfn[v]就行

#include 
using namespace std;
const int MaxN = 2e5 + 10;
int dfn[MaxN], low[MaxN], tot;
int cut[MaxN], root;
vector<int> e[MaxN
1
2
3
4
5