Tarjan全家桶系列--割点

割点定义

在无向图G=(V,E)中，如果一个节点u满足：删除u以及与u相关联的所有边后，图的连通分量数量增加，则称u为割点。

核心思想

Tarjan算法仍然基于深度优先搜索（DFS），利用两个关键数组：

• dfn[u]：节点u的DFS访问顺序（时间戳）
• low[u]：从u出发，不经过DFS树中的父节点，能到达的最小dfn值

判断割点的条件

对于一个节点u，有两种情况是割点：

情况1：u不是DFS树的根节点

如果存在u的一个子节点v，满足low[v] >= dfn[u]，那么u是割点。

解释：这意味着从v出发，在不经过u的情况下，无法到达u的祖先节点。移除u后，v及其后代将与图的其余部分断开。

情况2：u是DFS树的根节点

如果u有两个或更多个子树（在DFS树中），那么u是割点。

解释：作为根节点，每个子树之间没有连接（除了通过根节点）。移除根节点后，这些子树将互相断开。

模板

说明:Run(int _n,const vector<int>adj[])传入总点数n和vector<int>[]邻接表，运行tarjan求割点
vector<bool> Get()获取cut[]数组，cut[i]==true则i点是割点

template<intN>structCut_vertex{vector<bool>cut;//cut[i]==true,i是割点intdfn[N],low[N];constvector<int>*adj;intn,clk,root;voiddfs_t(intu){dfn[u]=low[u]=++clk;intcnt=0;//DFS树的u子树中,去掉u能新增的连通块数for(intto:adj[u]){if(dfn[to]==0){dfs_t(to);low[u]=min(low[u],low[to]);if(low[to]>=dfn[u])++cnt;}elselow[u]=min(low[u],dfn[to]);}if((u!=root&&cnt>=1)||cnt>=2)cut[u]=true;elsecut[u]=false;}voidRun(int_n,constvector<int>adj[]){n=_n;clk=0;cut.assign(n+3,false);fill(low,low+3+n,0);fill(dfn,dfn+3+n,0);this->adj=adj;for(inti=1;i<=n;++i)if(dfn[i]==0){root=i,dfs_t(i);}}vector<bool>Get(){returncut;}};constintmaxn=2*1e5+20;Cut_vertex<maxn>T;