割點

定義：

若一個點在圖中被去掉后，圖的連通塊個數增加，那么這個點就被稱為“割點”。如下圖所示紅點。

定義說白了就是若去掉一個點，圖被“斷開”的點稱為割點。

樸素算法：

• 枚舉每個點 u。
• 遍歷圖，如果有一個點或多個點遍歷不到（遍歷期間不能經過點 u），那么 u 就是割點。

時間復雜度：$O(N^2)$。

可作為對拍暴力程序。

正解：Tarjan

定義一些東西：

1. 時間戳：dfs 時表示每個點被遍歷到的“時間”，可用一個不斷增加的變量實現。記為 $dfn$。
2. 搜索樹：dfs 時由遍歷到的邊組成的樹（由于有打標記，所以不會重復訪問）。
3. 追溯值：以 u 為根的子樹中，所有不經過 u 能夠到達的節點的時間戳的最小值。記為 $low$。

關于追溯值：

結合張圖來理解：

設紅邊為搜索樹的邊，則 $3$ 號點因為有藍色的邊不經過他的父親 $2$ 號點，直接到達了 $1$ 號點，所以 $lo{w}_3=df{n}_1$。

回歸 Tarjan

有一個重要的概念：

一個點 u 如果是割點，那么它的子樹中的一些節點 v 的 $lo{w}_v$ 是大等于 $df{n}_u$ 的，因為它到不了上面（上面的意思是搜索樹中比 u 更早遍歷到的點集）。

顯然，$lo{w}_u$ 表示假設斷開點 u 孩子們還能遍歷到的最早時間戳。

若 $lo{w}_v\ge df{n}_u$ （v 是 u 的孩子），即 v 回不到 u 前，那么就表示 u 是割點。

有 $s$ 個這樣的 v 就代表斷開 u 可以把原先的連通圖變成 $s+1$ 個連通塊（u 上方也是一個）。

遍歷路上

對于每個點 u，遍歷到的兒子 v 有兩種可能：

1. $df{n}_v=0$?

說明 v 是新加入搜索樹中的節點，那么就先遞歸下去，用 $lo{w}_v$ 更新 $lo{w}_u$。

即 $lo{w}_u=min(lo{w}_u,lo{w}_v)$。

2. $df{n}_v\ne 0$

說明 v 曾經

被遍歷過，是搜索樹上 u 的祖先，那么用 $df{n}_v$ 更新 $lo{w}_u$。

即 $lo{w}_u=min(lo{w}_u,df{n}_v)$。

然而上述辦法還是有 bug。想想在哪呢？

發現 bug

假設我們搜索樹從 $1$ 號點開始遍歷，給張圖你就懂。

如圖。

因為我們是從 $1$ 號點開始遍歷的，$1$ 號點是搜索樹的根，它哪來的祖先能讓孩子們去更新追溯值啊！！！

而圖中的 $1$ 號點又顯然不是割點。

咋辦呢？

解決 bug

特判唄。反正根只有一個。

這時候我們得思考：什么樣的情況下根是割點？

反正追溯值做不了了。

那么看看樸素的圖吧。

圖中 $1$ 號點就是割點。

為啥嘞？

答：因為把它刪了后有兩個連通塊。

正解。

我們記錄一下，如果它在搜索樹上的兒子不止一個，那么它就是割點。

就這么簡單？

就這么簡單。

這時候不知道有沒有同學有個疑惑和我初學時一樣的，如圖：

紅色的是搜索樹邊。

圖中 $1$ 不是割點啊，但它在樹上還真有兩個孩子啊？？

如果您一開始沒看出來哪兒錯了，就點個贊再走吧。

注意到邊 $3\to 2$ 和 $1\to 2$。

當我們遍歷到點 $3$ 的時候，它就會順帶把 $2$ 號點先遍歷了。先遍歷到 $2$ 再遍歷 $3$ 同理。

所以說搜索樹應該為：

或：

OK，下班，看題。

洛谷 P3388 【模板】割點（割頂）。

題意很簡略了。就是看看實現。

#include<bits/stdc++.h>
using namespace std;
const int N=2e4+5,M=1e5+5;
int n,m,ehead[N],cnt_e,low[N],dfn[N],idx,rt,cntans;
bool ans[N];//是否為割點
struct E{int to,pre;
}e[M<<1];
void adde(int from,int to)
{e[++cnt_e].to=to;e[cnt_e].pre=ehead[from];ehead[from]=cnt_e;return;
}
void dfs(int u)
{low[u]=dfn[u]=++idx;int chtree=0;//如果是根的話，它的孩子個數for(int i=ehead[u];i;i=e[i].pre){int v=e[i].to;if(!dfn[v])//不在搜索樹上{dfs(v);low[u]=min(low[u],low[v]);if(rt==u)++chtree;if(low[v]>=dfn[u]&&rt!=u&&(!ans[u]))//注意 (!ans[u])。搞不好會重復算 cntans{++cntans;ans[u]=1;}}else//返祖邊low[u]=min(low[u],dfn[v]);}if(u==rt&&chtree>1&&(!ans[u])){++cntans;ans[u]=1;}return;
}
int main(){ios::sync_with_stdio(0);cin>>n>>m;for(int i=1,u,v;i<=m;++i){cin>>u>>v;adde(u,v);adde(v,u);}for(int i=1;i<=n;++i)//圖不保證聯通{if(!dfn[i]){rt=i;dfs(i);}}cout<<cntans<<'\n';for(int i=1;i<=n;++i)if(ans[i])cout<<i<<' ';cout<<'\n';return 0;
}

閑話時間

講個好玩的，這篇文章是我晚上十一點左右寫的，但是：

我來自報家門了。

正題。

Tarjan 算法不光能解決割點的問題，改一改還能當作強連通分量和割邊（又稱橋）和雙連通分量等等。

說到強連通分量，推銷一下我的學習筆記不過分吧 qwq。

完結撒花。