割点、割边(桥) tarjan

定义

割点：无向图删掉一点和它所关联的边，图的连通性增加。 割边(桥)：无向图删掉一边，图的连通性增加。

如何求割点？

求割点的时候分两种情况：

从根节点可以遍历整个图那么根节点就不是割点，否则就是割点。对于点$U$存在子节点$V$，$V$可以访问到$U$的父节点，那么点U就不是割点，否则就是割点。 int low[maxn], dfn[maxn], now, root = 1; vector<int> g[maxn]; set<int> ans; void init() { now = 0; mem(dfn, 0); mem(low, 0); } void addedge(int u, int v) { g[u].push_back(v); g[v].push_back(u); } void tarjan(int u, int fa) { low[u] = dfn[u] = ++now; int len = g[u].size(); int son = 0; for (int i = 0; i < len; ++i) { int v = g[u][i]; if (v == fa) continue; if (!dfn[v]) { tarjan(v, u); son++; low[u] = min(low[u], low[v]); if (u == root && son > 1) { ans.insert(u); }else if (u != root && dfn[u] <= low[v]){ ans.insert(u); } }else{ low[u] = min(low[u], dfn[v]); } } }

如何求割边？

割边等价于$dfn[u]<low[v]$

割点 poj1144 Accode 割边 UVA796 Accode