最近刚学习了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 <bits/stdc++.h>using namespace std;const int N = 100010;int dfn[N], low[N], idx;vector<int> g[N];set<int> 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].
看一道割边的题目华华和月月逛公园
题目中描述的不一定要走的边其实可以转化为不是割边的边，因为如果这条是割边，割去之后仍是连通图，与猜测不符。所以题目就转化为求n-割边的数目，非常简单的模板题。
#include<bits/stdc++.h>using namespace std;const int N = 100010;int dfn[N], low[N], idx;int n, m, ans;vector<int> 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++;}elselow[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;}
