缩点
有向图缩点（把一个强连通分量看成一个点），用于优化。
- 树枝边：DFS 时经过的边，即 DFS 搜索树上的边
- 反祖边：也叫回边或后向边，与 DFS 方向相反，从某个结点指
向其某个祖先的边 - 横叉边：从某个结点指向搜索树中另一子树中的某结点的边，它
主要是在搜索的时候遇到了一个已经访问过的结点，但是这个结
点并不是当前结点的祖先时形成的 - 前向边：与 DFS 方向一致，从某个结点指向其某个子孙的边，
它是在搜索的时候遇到子树中的结点的时候形成的
对于每个点维护两个值 \(（dfn，low）\) ，\(dfn\) 是 \(dfs\) 序，\(low\) 表示这条路走到头能回到祖宗的最小值（或叶子），对于一个点 \(u\) ，如果他的 \(low[u]\) 等于 \(dfn[u]\) ,说明 向下 \(dfs\) 时还能回到 \(u\) ，则中间这部分构成一个强连通分量。
如图，先 \(dfs\) 到 \(e\) ，\(dfn[e]==low[e]\)，发现一个强连通分量，\(e\) 出栈，回溯到 \(b\) ,第二个强连通分量，将 \(b,c,d\) 出栈。
缩完点变成有向无环图（DAG），可以跑最短路，可以dp，很方便。
code
void tj(int s)
{
dfn[s]=low[s]=++num;
v[s]=1; st.push(s);
for(int i=head[s];i;i=e[i].nxt)
{
int to=e[i].to;
if(!dfn[to])
{
tj(to);
low[s]=min(low[s],low[to]);
}
else if(v[to]) low[s]=min(low[s],dfn[to]);
}
if(dfn[s]==low[s])
{
int now;
t++;
do
{
now=st.top(); st.pop();
v[now]=0; bl[now]=t;
sz[t]++;
} while(s!=now);
}
}
int main()
{
…………
memset(head,0,sizeof(head)); tot=0;
for(int i=1;i<=m;i++)
if(bl[x[i]]!=bl[y[i]])
add(bl[x[i]],bl[y[i]]);
…………
}
割点
无向图求割点，就是删掉后能把图隔成几个部分的点，思路和缩点类似，如果 \(dfn[u]<=low[v]\) ,说明 \(u\) 以下有一个连通块，且 \(u\) 下面的连通块和 \(u\) 上面的没有联系，所以此时 \(u\) 为割点。
如图 \(B,E,K\) 为割点。
（注意，根节点如果只有一个儿子，他不是割点。）
code
void tj(int s)
{
dfn[s]=low[s]=++num;
int son=0;
for(int i=head[s];i;i=e[i].nxt)
{
int to=e[i].to;
if(!dfn[to])
{
tj(to);
low[s]=min(low[s],low[to]);
if(dfn[s]<=low[to])
{
son++;
if(s!=root || son>1)
{
if(!ans[s]) cnt++;
ans[s]=1;
}
}
}
else
low[s]=min(low[s],dfn[to]);
}
}
割边
无向图求割边，定义和割点差不多了，如 \(dfn[u]<low[v]\) 则 \((u,v)\) 为割边（注意不能 \(=\) ），上图割边有 \(A-B\)以及 \(E-K\) 和 \(K-L\) ,因为是无向图，建边时都建成了正向反向两条边，所以要判一下正向反向的两条边，避免原路走回去。
code
void tj(int s,int fa)
{
dfn[s]=low[s]=++num;
for(int i=head[s];i;i=e[i].nxt)
{
int to=e[i].to;
if(to==fa) continue;
if(!dfn[to])
{
tj(to,s);
low[s]=min(low[s],low[to]);
if(dfn[s]<low[to]) ans++;
}
else low[s]=min(low[s],dfn[to]);
}
}