博主图论比较弱，搜了模版也不会用。。。
所以决心学习下tarjan算法。
割点和割边的概念不在赘述，tarjan能在线性时间复杂度内求出割边。
重要的概念：时间戟，就是一个全局变量clock记录访问结点的时间。一个无向图dfs会形成一个森林，当图只有一个连通分量时，就只有一棵树。
由于在无向图中，除了树边，其他都是反向边。可以画个图感受一下，可以反证的，如果有其他类型的边，那么dfs先沿着那些边跑图的，那么那些边就不存在。
如果结点是树根，那么它是割点的充要条件就是它有两个子结点。
定理
对于其他结点，如果他的子结点的反向边没有指向它的祖先的，那么它就是割点。证明很明显，因为无向图是没有横跨子树的边的。（对树根不成立哦~）
具体判断的时候借助时间戟，定义low(u)为u和其后代所能返回最早祖先的的dfn值，那么定理就可以等价的转化为low(v)>=pre(u)。而且如果v的后代只能返回自己，那么删除(u,v)的一条边就可以让图分连通，那么就找到了割边（桥）。
伪代码
int dfs(int u,int fa) 返回u的low值, fa是判断是不是树边的二次访问
{
记录时间戟并初始化u的low值
跑图｛
如果子节点v没访问过｛
dfs(v)并返回后代low值
用后代low值更新u的low值
如果 后代的low值>=pre //根据要求的是割边还是割点替换判断条件
那么u是割点 //用数组记录，因为一个割点，条件可能不只成立一次
｝否则 如果是反向边 // 一.要满足v的时间戟小于u的，二.v不是u的父节点（是无向图的边的二次访问）
｛
用反向边更新u的low值
｝
｝
用数组记录low u
返回 low u
}
对于树根可以特判，可以通过对代码的小改动来实现，做法是记录子结点数量child，初始调用时fa赋值-1，加一个判断fa<0且child == 1时iscut（u） = false
这个不能跑重边
对于有重边的图可以采用以下技巧
如果是用前向星存正反两条边是相邻并且奇偶性一定是不一样的，那么可以利用异或的开关性，来判断是不是树边if(i==(id^1))continue;//不从i对应的边到父节点
void tarjan(int u,int fa) { dfn[u] = low[u] = ++clock; for(int i = head[i]; ~i ; i = nxt[i]){ int v = to[i]; if(!dfn[v]){ tarjan(v,u); low[u] = min(low[u],low[v]); if(low[v] > dfn[u]){ ans = min(ans,wei[i]) } }else if(v != fa) { low[u] = min(low[u],dfn[v]); } } }
如果从树根出发的话，那么有两个以上的结点，反而不是割边。（具体看想要连通哪里）