割点&割边 点双&边双
基础概念
定义
割点：在无向连通图中，若去掉某点（即去掉所有与之相连的边）后，该图不连通，则称这个点是割点。
割边：在无向连通图中，若去掉某边后，该图不连通，则称这条边是割边，也称桥。
点双连通图：不存在割点的图，两点一线除外。
边双连通图：不存在割边的图，两点一线除外。
点双：极大的点双连通图。
边双：极大的边双连通图。
性质
1.点双（除两点一线型）中任意两点间至少存在两条点不同的路径，即任意两点被包含在至少 1 个简单环中。
证明：若两点只存在一条点不同的路径，则路径上度大于 1 的点就是割点，与定义相违背。
2.割点连接着至少 2 个点双，非割点的点至多存在于 1 个点双中。这是显而易见的。
3.割边（除两点一线型）中任意两点间至少存在两条边不相同的路径，即任意一边都被包含于至少 1 个简单环中。
证明：同 1 的证法。否则点双会出现割边。
4.点双连通不具传递性（因为点会重合），边双连通具有传递性。
割点与割边的求法
这里要请出 Tarjan 大法了，在这之前，补充一些概念：
1.dfs 树：即 dfs 遍历得到的树，注意是有向的。
2.树边：dfs 树上由祖先节点指向儿子节点的边。
3.非树边：dfs 树上由儿子节点指向祖先节点的边。
割点
定义数组：
1.dfn[]：记录节点的 dfs 序。
2.low[]：记录节点经过至多 1 条非树边和若干条树边后所到点的 dfn 最小值。
类似求解强连通分量，维护上述数组。
关键是判定：令 v 为节点 u 的子节点，若
如何理解？回顾定义，显然
若满足判定条件，则说明 v 无法绕远路到达除 u 外已遍历的点，放在原图这代表 v 必须经过 u 才能到达这些点。于是去掉 u 后，原图不再连通，u 便是割点。
代码如下。
注意根节点的特判（若树上根节点的出边大于 1，则根节点为割点）。
void Tarjan(int k)
{
dfn[k]=low[k]=++df;
int ch=0;
for(int i=0; i<e[k].size();i++)
{
int v=e[k][i];
if(dfn[v]==0)
{
Tarjan(v);
low[k]=min(low[k],low[v]);
if(low[v]>=dfn[k]&&k!=root) //根节点特判
{
pt[k]=1; //pt数组标记割点
}
ch++;
}
else
{
low[k]=min(low[k],dfn[v]);
}
}
if(k==root&&ch>1) //当根节点是割点时，防止少算根节点
{
pt[k]=1;
}
}割边
除判定外与割点求法一致。若
为啥没有等于呢？关键是边双定义为 任意两点间至少存在两条边不同的路径，一点可连接多条边，看图有答案：
如上图，1、3 点之间的两条路径点相同，边不同。
点双
只需遍历时把所有点压入栈，遇到割点就不断弹出直到遇见割点，正确性的证明类比强连通分量。
需要注意的是，割点可能被多个点双包含，因此不能弹出但要记录。推荐写法：不断弹出到点 v，最后记录 u 即可。
代码如下。
void Tarjan(int k)
{
dfn[k]=low[k]=++df;
st.push(k);
int cnt=0;
for(int i=0; i<e[k].size();i++)
{
int v=e[k][i];
if(dfn[v]==0)
{
cnt++;
Tarjan(v);
low[k]=min(low[k],low[v]);
if(low[v]>=dfn[k])
{
ans++;
int p;
do
{
p=st.top();
st.pop();
answer[ans].pb(p); //answer数组记录点双
}while(p^v);
answer[ans].pb(k);
}
}
else
{
low[k]=min(low[k],dfn[v]);
}
}
if(cnt==0&&k==root) //判断孤立点
{
ans++;
answer[ans].pb(k);
return ;
}
}边双
可以求出每条割边，对其标记后再做 dfs 染色即可，但是比较复杂。
仔细想想，Tarjan 已经把无向图化为有向图，边不再具有不确定性。而边双可看作是环，环也是强连通分量，考虑仿照强连通分量的做法对图进行缩点。
区别在于有向图与无向图，无需判断子节点是否已在强连通分量中，vis 就没有存在的意义了。
解释上句：无向图的 dfs 树中不存在横叉边，所以不可能出现 v 在其他边双的情况。
代码如下：
void Tarjan(int fa,int k)
{
dfn[k]=low[k]=++df;
st.push(k);
int fl=0;
for(int i=0; i<e[k].size();i++)
{
int v=e[k][i];
if(fa==v&&fl==0) //判定重边
{
fl=1;
continue;
}
if(!dfn[v])
{
Tarjan(k,v);
}
low[k]=min(low[k],low[v]);
}
if(low[k]==dfn[k])
{
cnt++;
int p;
do
{
p=st.top();
st.pop();
ans[cnt]++; //记录大小
ans2[cnt].pb(p); //记录每个点
}while(p^k);
}
}具体应用
题目多与点双、边双有关。注意它们的区别，对题目进行点双缩点或边双缩点（模板）。当然，最重要的是结合其它知识。