复健发现自己对于 Tarjan 的一些东西都有些搞不清了啊。整理一下。
如有错误/不足，欢迎指出。
先给一些定义：
- \(u\) 表示某个子树的根节点。
- \(v\) 表示与 \(u\) 相连的点。如果是无向图那么不包含父亲。
- \(fa\) 表示 \(u\) 在 DFS 生成树上的父亲节点。
- \(dfn_u\)，表示 \(u\) 点的时间戳，即 \(u\) 点被搜索的次序。\(dfn_u\) 越小，那么被搜到的就越早。
- \(low_u\)，表示 \(u\) 子树中向外连至多一条非树边所能到达的最小 \(dfn\)。
我认为理解了 \(low_u\) 的定义就基本掌握 Tarjan 了。请牢记 \(low\) 的定义。
有向图的 DFS 生成树
这是一棵有向图 DFS 生成树。
有这几种边的类型：
- 树边（黑），DFS 过程中经过的边。
- 返祖边（红），指向祖先的边。
- 前向边（绿），由祖先指向子树内点的边。
- 横插边（蓝），两个没有祖先关系的点之间的连边。
- 非树边，字面意思，除了树边的边，即返祖边、前向边、横插边。
有向图中求强连通分量（SCC）
定义：SCC 中任意两点可以互相到达。
显然这两点在一个环中。
先给出实现：
void dfs(int u){dfn[u]=low[u]=++idx,ins[u]=1,s[++tp]=u;for(int v:G[u]){if(!dfn[v])dfs(v),cmn(low[u],low[v]);else if(ins[v])cmn(low[u],dfn[v]);}if(dfn[u]==low[u]){int p;++cnt;do p=s[tp--],ins[p]=0,fa[p]=cnt,val[cnt]+=a[p];while(p!=u);}
}
我们维护一个搜索栈，记录当前可能成为一个 SCC 的所有点。
考虑 \(low\) 数组的更新。遍历 \(v\)，有这几种情况：
- \(v\) 没被搜过。先搜 \(v\)，并更新 \(v\) 的信息，有
low[u]=min(low[u],low[v])。 - \(v\) 被搜过了。此时 \((u,v)\) 就是非树边。如果 \(v\) 不在栈内，那么 \(v\) 已经在其他 SCC 中了，被处理过了，不管。如果在栈内，就说明可以跟它在同一个 SCC 中（通过这条边和 \(v\) 已经在的 SCC 走到 \(u\) 的祖先，再走下来，成为了一个环），有转移
low[u]=min(low[u],dfn[v])。
让我们考虑什么时候会形成一个新的 SCC。在遍历完所有子树之后，\(u\) 的所有子树中的在栈内的点（包括 \(u\)）对应到原图上的子图是强连通的。有这两种情况：（下面所说的子树 \(u\) 内的点都表示子树 \(u\) 中在栈内的那些点）
- \(low_u<dfn_u\)，则子树 \(u\) 可以通过一条非树边到达 \(u\) 的祖先，然后再通过树边回到 \(u\)，成环。那么 \(u\) 和 \(fa\) 就是强连通的。又因为 \(u\) 的子树强连通，所以 \(fa\) 和子树 \(u\) 强连通。
- \(low_u=dfn_u\)，子树 \(u\) 无法回到 \(fa\) 及以上了，无法与 \(fa\) 强连通。此时就将栈中 \(u\) 及其子树都弹出，SCC 数 \(+1\)。显然栈中的数是升序的，\(u\) 及以后的都在 \(u\) 的子树内。
这些就是对上面实现比较详细的解释。
可能还有一个问题，第二个 low[u]=min(low[u],dfn[v]) 写作 low[u]=min(low[u],low[v]) 也能过。但是要注意这是 错误的。据我了解应该有挺多选手这样写的。
这样写 \(low_u\) 的定义应为经过若干条边能够到达的 \(dfn\) 最小的点。理论上，这样确实也是可做的。
但是注意到，如果搜的是一条反祖边，\(v\) 是祖先节点，此时 \(low_v\) 还在更新中，还没更新完，直接转移是无法得到你想要的 \(low_u\) 的。
但是因为有 \(low_u\le dfn_u\)，而且如果按照这个定义来讲，我们记正确的 \(low_u\) 为 \(low_{right_u}\)，那么有我们求出来的 \(low_u\in[low_{right_u},dfn_u]\)，而在取到这两个端点去做的时候是对的，所以 low[u]=min(low[u],dfn[v]) 写作 low[u]=min(low[u],low[v]) 也可以过。
无向图的 DFS 生成树
请自行将此图中的有向边视为无向边。
相较于有向图的 DFS 生成树，有些许不同。
- 没有了反祖边和前向边之分。由于边无向，这两者就成一个概念了。
- 不存在横插边。由于边无向以及 DFS 的性质，显然你搜一个子树肯定会把往外的所有边都搜完，不会留给你横插边让你在另外一个地方搜的。
所以，我们可以认为无向图的 DFS 生成树中只有树边和非树边之分。
无向图的 DFS 生成树中，\(u\) 的所有子树之间都没有连边。
无向图中求割点
定义：去掉割点后原图的连通块数量会增加。
举例：这张图中 \(2\) 是割点。
现在我们对 \(low_u\) 的定义回到 \(u\) 子树中向外连至多一条非树边所能到达的最小 \(dfn\)。
考虑什么时候一个点是割点。根据定义，如果一个点的某两个子树之间在原图上没有边相连，那么这个点去掉之后连通块数量会增加。放到 DFS 生成树上去看，那么就是 \(low_v\le dfn_u\)，即子树 \(v\) 无法通过非树边到达 \(u\) 以上的位置，无法跟向上的子树有连边。
至于为什么不考虑下面的子树之间没有连边，在进行过上面的操作之后，如果所有子树都与那个向上的子树有连边，显然去掉 \(u\) 以后连通块数量不会增加。否则在上面已经记录过了。我们只需要判断一个点是不是割点即可，不需要考虑去掉它之后将会形成几个连通块。
那此时的 \(low\) 的转移就应该是 low[u]=min(low[u],dfn[v]) 了。
考虑一下为什么，定义 \(low\) 为走若干条边能到达的最小 \(dfn\)，使用 low[u]=min(low[u],low[v]) 的转移在此时是错的。
首先这是无向图，你可以自由移动到任何一个点。
那如果我们不走与父亲相连的边呢？这样还对吗？
可能存在子孙节点通过非树边来到了割点的情况，此时你还是能走到任意一个节点。
而且根据上面 SCC 部分的解释，这个更加错完了。
所以这样的定义是完全错误的。
此时需要特判整个树的根节点，因为它上面没有点了，只能考虑子树之间的贡献。
先看实现：
void dfs(int u,int fa){dfn[u]=low[u]=++idx;int son=0;for(int v:G[u]){if(v==fa)continue;if(!dfn[v]){dfs(v,u),++son,cmn(low[u],low[v]);if(fa&&low[v]>=dfn[u])fl[u]=1;}else cmn(low[u],dfn[v]);}if(!fa&&son>1)fl[u]=1;
}
其实上面已经讲的差不多了。\(low\) 的更新同有向图中求 SCC 的。
无向图中求割边（桥）
定义：去掉割边后原图的连通块数量会增加。
举例：这张图中 \((1,2)\) 是割边。
理解了割点的求法割边也就很好理解了。
同样的考虑什么时候一条边是割边。根据定义，如果一条边两端的子树在原图上没有连边，那么这条边去掉之后连通块数量会增加。放到 DFS 生成树上去看，那么就是 \(low_v>dfn_u\)，即子树 \(v\) 无法通过非树边到达 \(u\) 及以上的位置，无法跟向上的子树有连边。
显然此时不用判什么根节点了。
实现根求割点差不多。注意如果有重边的话，我们记录的不是 \(fa\)，是下来的那条边的编号，那条重边我们也是可以走的。
无向图中求边双连通分量
定义：边双连通图中去掉一条边之后，连通块数量不会增加。边双连通分量是极大的边双连通子图。
显然这条边不能是割边。换句话说，是割边将边双连通分量分开来了。
所以一种做法就是，求出所有的割边，然后删掉割边去求连通块。
甚至还要一遍 DFS，还要记录割边，太麻烦了。
我们考虑将 DFS 生成树上的树边定向为从 \(dfn\) 小的连向 \(dfn\) 大的（从上往下），非树边定向为 \(dfn\) 大的连向 \(dfn\) 小的（从下往上的反祖边），此时这个新图的 SCC 即原图的边双。
如何证明？不难发现，两个点 \(u,v\) 在一个边双中，当且仅当两点存在一个环中，环上断一条边显然没有任何影响。两个点 \(u,v\) 在一个 SCC 中，当且仅当两点在一个环中，显然这时两点可以互相到达。
对于无向图的 DFS 生成树，如果要找一个环，根据上面 \(low\) 的定义和更新方式，你显然是通过“往上走”的方式去走一条非树边的，否则没有什么意义。
然后你就发现，定向完之后跟 SCC 的做法是一样的。所以就跟 SCC 一样做即可。
注意重边。
看看实现：
void dfs(int u,int pr){dfn[u]=low[u]=++idx,ins[u]=1,s[++tp]=u;for(pii i:G[u]){int v=i.fi,id=i.se;if(id==pr)continue;if(!dfn[v])dfs(v,id),cmn(low[u],low[v]);else if(ins[v])cmn(low[u],dfn[v]);}if(dfn[u]==low[u]){int p;++cnt;do p=s[tp--],ins[p]=0,ans[cnt].pb(p);while(p!=u);}
}
几个注意点：
- 同 SCC 部分，这里的第二个
low[u]=min(low[u],dfn[v])写作low[u]=min(low[u],low[v])也是对的。为了方便记忆，不与其他的搞混，建议写前者。 - 因为不存在横插边，所以可以不记 \(ins\) 数组。
无向图中求点双连通分量
定义：点双连通图中去掉一个点之后，连通块数量不会增加。点双连通分量是极大的点双连通子图。
显然这个点不是割点。换句话说，是割点将点双连通分量分开来了。
先看实现：
void dfs(int u,int fa){if(!SZ(G[u])){ans[++cnt].pb(u);return;}dfn[u]=low[u]=++idx,s[++tp]=u;for(int v:G[u]){if(v==fa)continue;if(!dfn[v]){dfs(v,u),cmn(low[u],low[v]);if(low[v]>=dfn[u]){int p;++cnt;do p=s[tp--],ans[cnt].pb(p);while(p!=v);ans[cnt].pb(u);}}else cmn(low[u],dfn[v]);}
}
实现跟求割点的也差不多，就是搜到割点的时候弹出栈内 \(u\) 之前的点，注意割点会被多个点双共用，所以在割点作为根的时候不弹出，当然也不要忘记后面加入答案。
注意孤点。
)
)
)
