\(dfs\) 树及其他概念
在这样一棵由在图上进行 \(dfs\) 所形成的 \(dfs\) 树中，我们注明了三种边。
黑色的边为 树边。
绿色的边为 前向边，由一个节点指向它子树上的节点。
红色的边为 返祖边，由子树上的节点指向其父节点。这条边上的终点比这条边上的起点先被访问。
蓝色的边为 横叉边，由一个节点指向 \(dfs\) 树上既非其子节点，又非其父节点的点。这条边的终点比起点先被访问。
后三种边统称为非树边。
小结论1：无向图中没有横叉边。在给出的这个 \(dfs\) 树中，我们假设所有的边都是无向边，那么当搜索到 \(7\) 节点时，显然可以继续搜索 \(9\) 节点，\(9\) 节点因此成为了 \(7\) 节点的子节点。因此不会存在横叉边。
小结论2：如果点 \(u\) 是某个强连通分量在 \(dfs\) 中第一次遇到的点，那么这个强连通分量的其它点必定在 \(dfs\) 树上 \(u\) 的子树中。
强连通性
首先，强连通性只是针对有向图的说法。如果在一个有向图中，从 \(u\) 出发能到 \(v\)，且从 \(v\) 出发能到 \(u\)，那么我们就称 \(u\) 和 \(v\) 强连通。强连通性满足传递性，自反性，对称性。我们可以根据点与点是否是强连通的将有向图中的节点划分成几个类，每个类中的节点两两强连通。这样的一个类我们称作强连通分量。
如何求出有向图中的强连通分量？这里引入 \(tarjan\) 算法。
在这个算法中，最核心的是 \(dfn\) 和 \(low\) 这两个数组。\(dfn[i]\) 表示 \(dfs\) 搜索到该节点的时间，而 \(low[i]\) 表示在 \(i\) 节点及其子树中所有节点，只走一条非树边所能到达的最早的时间戳。显然，\(low\) 数组可以通过递推得到。
每搜索到一个新的节点，我们都把这个点扔到栈里去。我们假设 \(v\) 为当前节点 \(u\) 经过一条边——树边也好，非树边也好，所到达的节点。假如点 \(v\) 为 \(u\) 子树上的节点，那么由小结论2可知，\(v\) 能到的点 \(u\) 肯定能到，如此自底向上地进行更新，因此此时有：
\[low[u] = min(low[u],low[v]) \]假设 \(v\) 没在 \(u\) 的子树上，那么就这样更新：
\[low[u] = min(low[u],dfn[v]) \]当我们将 \(low[u]\) 算出来后，只需比较一下 \(low[u]\) 是否等于 \(dfn[u]\)，如果二者相等，说明其子树里的节点无论如何也不能到达比 \(u\) 更早的节点。那么就反复弹栈，直到弹出 \(u\) 为止，弹出的所有节点为一个强连通分量。我们可以利用它来进行缩点。
void tarjan(int u){
low[u] = dfn[u] = ++tim;
node[++node[0]] = u;
vis[u] = 1;
for(int i = head[u]; i != 0; i = edge[i].next){
int v = edge[i].v;
if(!dfn[v]){
tarjan(v);
low[u] = min(low[u],low[v]);
}
else if(vis[v]){
low[u] = min(low[u],dfn[v]);
}
}
if(low[u] == dfn[u]){
++cnt;
while(node[node[0] + 1] != u){
color[node[node[0]]] = cnt;
sum[cnt] += a[node[node[0]]];
vis[node[node[0]--]] = 0;
}
}
}
另一种算法——\(Kosaraju\)。
重连通性a
边双连通：
对于 \(u\) \(v\) 两个节点，如果任意删除一条边，两个节点仍然连通，那么我们称这两个点边双连通。具有传递性、自反性、对称性。
点双连通：
对于 \(u\) \(v\) 两个节点，如果任意删除除他们以外的一个节点，两个节点仍然相连通，那么我们称这两个点点双连通。
割点：
删除一个点后，总连通分量数增加，就称这个点为割点。
割边（桥）：
删除一条边后，总连通分量数增加，称这个点为割边。
先看如何求割点，同样的，这也能用 \(tarjan\) 算法来实现。
求割点的 \(tarjan\) 中，我们不需要栈。对于非根节点的点 \(u\)，假如它有一个儿子 \(v\)，使得 \(low[v] >= dfn[u]\)，那么将 \(u\) 割掉后，其子树内的节点就无法到达更早的节点， \(u\) 便为 割点。如果是在无向图上求割点，需要注意在更新 \(low[v]\) 时，枚举的边的终点不能为 \(u\)。
对于根节点来说，如果其儿子数量大于 \(1\)，割掉后 \(dfs\) 就会分裂，此时根节点也符合割点。
void tarjan(int u,int fa){
low[u] = dfn[u] = ++tim;
int kid = 0;
for(int i = head[u]; i; i = edge[i].next){
int v = edge[i].v;
if(!dfn[v]){
tarjan(v,fa);
low[u] = min(low[u],low[v]);
if(low[v] >= dfn[u] && u != fa)ans.push_back(u);
if(u == fa)kid++;
}
else low[u] = min(low[u],dfn[v]);
}
if(kid >= 2 && u == fa)ans.push_back(u);
}
再看怎么求割边，仍是 \(tarjan\)。
原理类似求割点，只需将判断条件改为 \(low[v] > dfn[u]\) 即可。如果满足这个条件， \(u-v\) 这条边就是一条割边。如果是在无向图上求桥，需要注意在更新 \(low[v]\) 时，枚举的边的终点不能为 \(u\)。
无向图求桥：
void tarjan(int u,int fa){
low[u] = dfn[u] = ++tim;
int k;
for(int i = head[u]; i; i = edge[i].next){
int v = edge[i].v;
if(v == fa){
k = i;
continue;
}
if(!dfn[v]){
tarjan(v,u);
low[u] = min(low[u],low[v]);
if(low[v] > dfn[u])bridge[++bridge[0]] = i;
}
else low[u] = min(low[u],dfn[v]);
}
if(low[u] > dfn[fa])bridge[++bridge[0]] = k;
}
如此，求点双、边双就变得简单了。
把所有桥去掉，图中的每个连通块都是（极大）边双连通分量。
求点双时，仍用一个栈记录访问的节点，如果发现 \(u\) 的一个子节点 \(v\) 满足 \(u\) 是一个割点，那么反复弹栈直到弹出 \(v\)，弹出的这一堆和点 \(u\) 为一个（极大）点双连通分量。
void tarjan(int u){
low[u] = dfn[u] = ++tim;
sta[++sta[0]] = u;
for(int i = head[u]; i; i = edge[i].next){
int v = edge[i].v;
if(!dfn[v]){
tarjan(v);
low[u] = min(low[u],low[v]);
if(low[v] >= dfn[u]){
++cnt;
while(sta[sta[0] + 1] != v){
int k = sta[sta[0]--];
ans[cnt].push_back(k);
}
ans[cnt].push_back(u);
}
}
else low[u] = min(low[u],dfn[v]);
}
}
一个结论：割点至少属于两个极大点双连通分量，非割点只属于某一个极大点双连通分量。
标签：连通,连通性,int,tarjan,问题,dfn,low,节点 From： https://www.cnblogs.com/CZ-9/p/17068968.html