一下许多内容摘自：
北京大学暑期课《ACM/ICPC竞赛训练》强连通分支、桥和割点 北京大学信息学院 郭炜
还有很多网上神牛们的讲解/论文。
不过可能在摘录，或者加自己的见解时产生错误，望指出，谢谢！
之前只学了个强连通Tarjan算法，然后又摸了缩点操作；
然后今天在lightoj摸了一道模板题，是求所有桥的题；
然后发现，要把（割点，桥，双连通分量，最小割边集合，割点集合）都理一理呀！
割点
在一个无向连通图里面，删除这个点+这个点所连出去的边，图变成了不连通，就说这个点是割点。
割边（桥）
如果删除某边后，图变成不连通，则称该边为桥。
求割点和桥
求割点：我遍历所有的点，判断一下图是不是不连通了。复杂度？？？（认真脸 因为暴力，所以优化啊。
在深度优先遍历整个图的过程中形成一棵搜索树（思路和有向图求强连通分量类似 ）: Dfn[u]定义和Tarjan算法一样，表示编号为i的节点在DFS过程中 的访问序号(也可以叫做开始时间）。 Low[u]定义为u或者u的子树中能够通过非父子边（父子边就是搜索树上的边），追溯到的最早的节点的DFS开始时间；
等等，我们说这个Low[u]的定义与有向图的Tarjan算法不同，那，有向图Tarjan算法中Low[u]的定义是？ 表示从i节点出发DFS过程中i下方节点(开始时间大于Dfn[i]，且由i可达的节点）所能到达的最早的节点的开始时间。初始时Low[i]=Dfn[i]。
一个顶点u是割点，当且仅当满足(1)或(2) (1) 是树根（其实这个根就一个，就是最先进去的点），且u有多于一个子树。 (2) u不为树根，且存在(u,v)为树枝边（或称父子边，即u为v在搜索树中的父亲），使得dfn(u) <= low[v];
非树枝边不可能是桥 一条边(u,v)是桥，当且仅当(u,v)为树枝边，且满足dfn(u) < low(v)（前提是其没有重边）。
伪代码
Tarjan(u)
{
dfn[u]=low[u]=++index;
for each (u, v)
in E
{
if (v
is not visted){
tarjan(v)
low[u] = min(low[u], low[v])
dfn[u]<low[v] <
=> (u, v) 是桥
}
else
{
if(v 不是u 的父节点)
low[u] = min(low[u], dfn[v])
}
}
if (u
is root)
u 是割点 <
=> u 有至少两个子节点
else
u 是割点 <
=> u 有一个子节点v，满足dfn[u]<= low[v]
}
我斌模板理解：
const
int N=
1e4+
10;
const
int M=
2e4+
10;
struct Edge{
int to;
int next;
};
Edge
q[M*2];
int head[M
*2],tol,n,
m;
int dfn[N],low[N];
int ind,top;
bool flag[N],vis[N];
void init()
{
tol=
0;
memset(head,-
1,sizeof(head));
}
void add(
int u,
int v)
{
q[tol].to=v;
q[tol].
next=head[u];
head[u]=tol++;
}
void Tarjan(
int u,
int pre)
{
int v;
int son=
0;
low[u]=dfn[u]=ind++;
vis[u]=true;
for(
int i=head[u];i!=-
1;i=
q[i].
next)
{
v=
q[i].to;
if((i^
1) == pre)//去重操作；这样处理是单单处理了“一条无向边”，两个结点的“多条边”的地位是等价的，
continue;
//如果你记录前驱结点，判断掉你只会处理两个结点的“多条边”其中的“一条边”
if(!dfn[v])
{
son++;
Tarjan(v,i);
if(dfn[u] < low[v])
{
//桥；
}
low[u]=min(low[v],low[u]);
if(u!=pre&&low[v]>=dfn[u])//不是树根，且存在(u,v)为树枝边。
flag[u]=true;
}
else
low[u]=min(low[u],dfn[v]);
}
if(pre==u&&son>
1)//是树根，且存在两棵子树
flag[u]=true;
}
void qiugedian()
{
//各种初始化；
memset(dfn,
0,sizeof(dfn));
memset(low,
0,sizeof(low));
memset(flag,
0,sizeof(flag));
ind=
1;
Tarjan(
1,
1);
//我们随便设个
1作为树根，图上任意点都行，无所谓；
int ans=
0;
for(
int i=
1;i<=n;i++)//计算割点个数
if(flag[i])
ans++;
}
点双连通分量
割点集合：在无向连通图里，如果有一个顶点集合，删除这个顶点集合，以及这个集合所有顶点相关联的边，原图变成多个联通块，就称这个点集称为最小割点集合（割集）。 点连通度：最小割点集合的顶点数。 点双连通分量：点连通度 > 1
我*，长啥样啊！ 图片来自知乎 PS: 双连通也称重连通
求点双连通分支
求割点的过程中，顺便把每个点的点双连通分量求出来。 利用 栈 存当前的点双连通分支： 1. 树枝边（就是结点u连出的结点v的边，结点v还没有访问过） 2. 反向边（连到树中祖先的边） 如果遇到某 树枝边（u,v) 满足dfn(u)<=low(v)，说明u是一个割点，此时把边从栈顶一个个取出，直到遇到了边(u,v)，取出的这些边与其关联的点，组成一个点双连通分支。 割点可以属于多个点双连通分支。
边双连通分量
割边集合：在无向连通图里，如果有一个边集合，删除这个边集合，原图变成多个联通块，就称这个边集称为割边集合。 边连通度：最小割边集合中的边数。 边双连通分量：边连通度>1
我*，又长啥样啊！
求边双连通分支
把图中的所有桥求出，把桥边删除，原图就变成了多个连通块，则每个块就是一个边双联通分量。 桥不属于任何一个边双连通分支。
