图论|tarjan算法之——割点和桥图论|tarjan

最近刚学习了tarjan算法，发一篇博客写一下自己的心得和理解。
在了解割点和桥之前，我们先理解什么是双连通。
双连通和强连通分别是应用于无向图和有向图中的，那么在学习双连通之前，请自行学习求强连通分量的tarjan算法。
在一张连通的无向图中，如果删去任意的一条连接u,v的边，但u, v仍然可以保持连通，那么我们可以称u,v之间是边双连通的。
在一张连通的无向图中，如果删去任意的一个连接u,v的点，但u,v之间仍是连通的，那么我们可以称u,v之间是点双连通的。

文章图片

接着我们来认识割点和桥
比如在这张图中，如果删去u或v节点，那么图中的连通分量将会增加，因此可以称u和v是这张无向图中的割点；相对应的，如果删去连接u，v的那条边，那么图中的连通分量也会增加，因此我们称连接u,v的边为桥。
割点
在求割点时，我们要分两种情况：当前求得割点是否为根。
1.如果当前所求的点为根，那么我们只需要计算根的儿子节点数，如果大于等于2即可说明根为割点。
2.如果当前所求的点不为根，那么我们只要判断在当前点的所有儿子节点中，如果有一个儿子节点无法凭借除了父亲节点之外的点回到祖先节点，那么这个儿子节点的父亲节点就是割点。
借助一张图说明

文章图片

如果u的儿子属于第一区域，他可以有别的路径回到祖先节点，那么u就不是割点。
如果u的儿子属于第二区域，他除了经过父亲节点外无法回到祖先节点，那么u就是割点
那么理解完割点的定义后，如何求解？
和tarjan算法一样，定义一个DFN为一个节点的时间戳，即dfs序，定义LOW为能返回的最早的时间戳。
如果这个节点u为非根节点，那么当这个点的儿子v的LOW[v] >= DFN[u]时，即无法返回到祖先节点，那么u就是一个割点。
当这个点为祖先节点时，如何求他的儿子个数呢？只要在每一次dfs回溯到根时，即u==root时，给孩子节点++即可。
接下来看一道割点的模板题洛谷3388

#include using namespace std; const int N = 100010; int dfn[N], low[N], idx; vector g[N]; set st; int n, m; void tarjan(int u, int root, int fa) { dfn[u] = low[u] = ++idx; int child = 0; for (auto v : g[u]) { if (!dfn[v]) { tarjan(v, root, u); low[u] = min(low[u], low[v]); if (low[v] >= dfn[u] && u != root) st.insert(u); if (u == root) child++; } else if(v != fa) low[u] = min(low[u], dfn[v]); } if (child >= 2 && u == root) st.insert(u); }int main() { cin >> n >> m; for (int i = 0; i < m; i++) { int x, y; cin >> x >> y; g[x].push_back(y); g[y].push_back(x); } for (int i = 1; i <= n; i++) if (!dfn[i]) tarjan(i, i, 0); cout << st.size() << endl; for (auto x : st) cout << x << " "; }

桥
和割点差不多，只要改一处LOW[v] > DFN[u] 就可以了，而且不需要考虑根节点的问题。
割边是和是不是根节点无关，原来我们求割点的时候是指儿子节点是不可能不经过父节点回到祖先节点（包括父节点），所以顶点u是割点。但桥的判定中，如果桥还可以回到父节点，那么说明删除了u,v之间的边仍不能让连通分量增加，因此必须要求LOW[v] > DFN[u].
看一道割边的题目华华和月月逛公园
【图论|tarjan算法之——割点和桥】题目中描述的不一定要走的边其实可以转化为不是割边的边，因为如果这条是割边，割去之后仍是连通图，与猜测不符。所以题目就转化为求n-割边的数目，非常简单的模板题。

#include using namespace std; const int N = 100010; int dfn[N], low[N], idx; int n, m, ans; vector g[N]; void tarjan(int u, int fa) { dfn[u] = low[u] = ++idx; for (auto v : g[u]) { if(v == fa) continue; if (!dfn[v]) { tarjan(v, u); low[u] = min(low[u], low[v]); if (low[v] > dfn[u]) ans++; } else low[u] = min(low[u], dfn[v]); } }int main() { cin >> n >> m; for (int i = 0; i < m; i++) { int x, y; cin >> x >> y; g[x].push_back(y); g[y].push_back(x); } tarjan(1, 0); cout << m - ans; }