都口胡了求割边,就顺便口胡求割点好了QAQ
的定义同求有向图强连通分量.
枚举当前点的所有邻接点:
1.如果某个邻接点未被访问过,则访问,并在回溯后更新
2.如果某个邻接点已被访问过,则更新
对于当前节点,
如果为搜索树中的根节点,若它的子节点数(根是多棵子树上节点的唯一连通方式),则为割点;
如果为搜索树上的非根节点,若存在子节点满足(向上无法到达的祖先),则为割点.
inline void tarjan(int u,int fa){
dfn[u]=low[u]=++cnt;
for(int i=g[u];i;i=e[i].nxt){
++t[u];
if(!dfn[e[i].to]){
tarjan(e[i].to,u);
low[u]=min(low[u],low[e[i].to]);
if(u==1){
if(t[u]>=2) cut[u]=true;
}
else if(low[e[i].to]>=dfn[x]) cut[u]=true;
}
else if(e[i].to!=fa)
low[u]=min(low[u],dfn[e[i].to]);
}
}