有向图
搜索树
对有向图进行 \(dfs\) 时，递归经过的有向边形成的树，被称为搜索树。
树边：边 \((x,y)\) 在搜索树中。
前向边：搜索树中存在一条 \(x\) 到 \(y\) 的路径。
后向边：搜索树中存在一条 \(y\) 到 \(x\) 的路径。
横叉边：搜索树中不存在 \(x\) 到 \(y\) 的路径和 \(y\) 到 \(x\) 的路径，且 \(dfn_y<dfn_x\)。
强连通分量
强连通图：在有向图中，对于每一对 \(x,y,x \not = y\)， 都存在从 \(x\) 到 \(y\) 的路径和从 \(y\) 到 \(x\) 的路径，则该有向图为强连通图。
强连通分量：有向图中的极大强连通子图。
可以用 \(Tarjan\) 算法 \(O(n+m)\) 来求有向图的强连通分量。
若点 \(x\) 为其所在的强连通分量在搜索树中第一个搜索到的点，称其为该强连通分量的根。
\(dfn_x\)：点 \(x\) 的 \(dfs\) 序，即 \(dfs\) 中第一次搜索到点 \(x\) 的次序。
\(low_x\)：在以点 \(x\) 为根的子树内的点通过非树边的一条边到达的 \(dfn\) 最小的节点 \(y\) 的 \(dfn\) 值，\(y\) 能到达 \(x\)。
\(st\)：栈内元素为当前已访问过但没有判定为在某个强连通分量的点。
\(vis_x\)，表示点 \(x\) 是否在栈中，用来判定一条边是否为返祖边。
当点 \(x\) 满足 \(dfn_x=low_x\) 时，其为其所在的强连通分量的根。
当枚举点 \(x\) 的出边 \((x,y)\) 时，若 \(y\) 为通过树边到达，则用 \(low_y\) 更新 \(low_x\)，若 \(y\) 为通过非树边到达，则用 \(dfn_y\) 更新 \(low_x\)。
void tarjan(int x)
{
dfn[x]=low[x]=++dfn_cnt,st[++top]=x,vis[x]=true;
for(int i=head[x];i;i=e[i].nxt)
{
int y=e[i].to;
if(!dfn[y]) tarjan(y),low[x]=min(low[x],low[y]);
else if(vis[y]) low[x]=min(low[x],dfn[y]);
}
if(low[x]==dfn[x])
{
col_cnt++;
int now;
do now=st[top--],vis[now]=false,col[now]=col_cnt; while(now!=x);
}
}
......
for(int i=1;i<=n;++i)
if(!dfn[i])
tarjan(i);
无向图
点双连通分量
割点：无向连通图中，如果将其中一个点以及所有连接该点的边去掉，图分裂为两个或两个以上的子图，则称该点为割点。
点双连通图：没有割点的无向连通图。
点连通分量：无向图中的极大点双连通子图。
选定一个根节点，从该根节点开始用 \(dfs\) 遍历整个图。
对于根节点，若其有两棵即以上的子树，则根节点为割点。因为如果去掉这个点，这两棵子树就不能互相到达。
对于非根节点 \(x\)，存在边 \((x, y)\)，如果 \(dfn_x \leqslant low_y\)，则 \(x\) 为割点。因为从 \(y\) 到以 \(x\) 为根的子树之外的点都必须经过点 \(x\)。
void tarjan(int x,int root)
{
int son=0;
dfn[x]=low[x]=++dfn_cnt;
for(int i=head[x];i;i=e[i].nxt)
{
int y=e[i].to;
if(!dfn[y])
{
tarjan(y,root),low[x]=min(low[x],low[y]);
if(x!=root&&dfn[x]<=low[y]) cut[x]=true;
if(x==root) son++;
}
else low[x]=min(low[x],dfn[y]);
}
if(son>1) cut[x]=true;
}
......
for(int i=1;i<=n;++i)
if(!dfn[i])
tarjan(i,i);
求割点时维护一个栈即可求出每个点双连通分量。
当 \(x\) 满足为割点时，就依次弹栈，直到弹出 \(y\) 就停止，\(x\) 还需留在栈中，因为割点 \(x\) 可能属于多个点双连通分量。
void tarjan(int x)
{
dfn[x]=low[x]=++dfn_cnt,st[++top]=x;
for(int i=head[x];i;i=e[i].nxt)
{
int y=e[i].to;
if(!dfn[y])
{
tarjan(y),low[x]=min(low[x],low[y]);
if(dfn[x]<=low[y])
{
col_cnt++;
int now;
do now=st[top--],col[now]=col_cnt; while(now!=y);
}
}
else low[x]=min(low[x],dfn[y]);
}
}
边双连通分量
桥：无向连通图中，如果一条边去掉，图分裂为两个子图，则称该边为桥。
边双连通图：没有桥的无向连通图。
边连通分量：无向图中的极大边双连通子图。
对于点 \(x\)，存在边 \((x, y)\)，如果 \(dfn_x < low_y\)，则边 \((x,y)\) 为桥。因为以 \(y\) 为根的子树内的点都必须经过边 \((x,y)\)。
记录入边 \(link\) 的作用是不处理儿子到父亲边，对于边 \((x,y)\)，若处理了儿子到父亲边，\(low_y\) 就会等于 \(dfn_x\)，将无法判定桥，记录具体是哪一条入边是为了处理重边的情况。
求出桥后即可求出边双连通分量。
void tarjan(int x,int link)
{
dfn[x]=low[x]=++dfn_cnt;
for(int i=head[x];i;i=e[i].nxt)
{
int y=e[i].to;
if(!dfn[y])
{
tarjan(y,i),low[x]=min(low[x],low[y]);
if(dfn[x]<low[y]) bri[i]=bri[i^1]=true;
}
else if(i!=(link^1)) low[x]=min(low[x],dfn[y]);
}
}
void dfs_col(int x)
{
col[x]=co_cnt;
for(int i=head[x];i;i=e[i].nxt)
{
int y=e[i].to;
if(col[y]||bri[i]) continue;
dfs_col(y);
}
}
......
for(int i=1;i<=n;++i)
if(!dfn[i])
tarjan(i,0);
for(int i=1;i<=n;++i)
if(!col[i])
col_cnt++,dfs_col(i);
给定一个无向连通图，至少添加多少条边可以把它变为边双连通图。
先对边双连通分量进行缩点，得到一棵无根树，设该树度数为 \(1\) 的节点个数为 \(cnt\)，则将该树变为边双连通图至少添加 \(\frac{cnt+1}{2}\) 条边。
在叶子节点带权下求出树的带权重心，然后将不同子树内的节点两两配对连边即可，因为一个子树内的叶子节点个数不超过 \(\frac{cnt}{2}\)，因此一定能匹配完后覆盖所有边。