一、强连通分量（Strongly Connected Components，SCC）
Tarjan的板子(求指正)
void Tarjan(int u)
{
dfn[u] = ++cnt; //节点u的时间戳+1
low[u] = cnt; //初始化：回到的最小时间戳节点是自己
stk[++top] = u;//手写栈，让u入栈
for(auto v : E[u])
{
if(!dfn[v])
{
Tarjan(v);//没访问过就对下一个节点进行一次dfs
low[u] = min(low[u],low[v]);
//暂时对下一个节点的low与自己的low进行toMin操作，让一条链上的节点附属同一个根
}
//rt[i] == j表示：节点i属于以j为根节点的强连通分量
else if(!rt[v]) //下一个节点不是根，即在栈内，即回到一个环的开头
low[u] = min(low[u],dfn[v]);
//看看自己的low换成环首的时间戳能不能更小，同时在回溯时影响自己的上一个节点
}
if(low[u] == dfn[u])//发现u是环首/祖宗
{
rt[u] = u;//计入数组root
while(stk[top] != u)//栈顶到u的所有元素都同属一个强连通分量
{
rt[stk[top]] = u;
top--;
}
top--;
}
}
下面是78AI豆包写的注释
// Tarjan算法核心函数：寻找以u为起点的强连通分量（SCC）
// 基于DFS遍历，通过维护时间戳dfn和回溯值low来识别SCC
// 当low[u] == dfn[u]时，栈中从u到栈顶的所有节点构成一个SCC
void Tarjan(int u)
{
dfn[u] = ++cnt; // 节点u的发现时间戳
low[u] = cnt; // 初始化low值为当前时间戳，代表u能回溯到的最早节点是自身
// 后续在DFS回溯过程中会被更新为更小的值（若存在环）
stk[++top] = u; // 压入栈中，表示进入当前DFS路径
for(auto v : E[u]) // 遍历u的所有邻接节点v
{
if(!dfn[v]) // v未被访问过
{
Tarjan(v); // 递归访问子节点v
low[u] = min(low[u], low[v]); // 回溯时更新u的low值：
// 若v能通过子树回溯到更早节点，则u也能通过v回溯到该节点
}
else if(!rt[v]) // v已被访问且仍在栈中（未被弹出），说明存在反向边u→v
low[u] = min(low[u], dfn[v]); // 将u的low值更新为v的发现时间戳：
// 表示u可以通过反向边回到更早的节点v
// 注意：此处必须用dfn[v]而非low[v]，避免跨SCC的干扰
if(low[u] == dfn[u]) // 若u的low值等于dfn值，说明u无法通过子树或反向边回溯到更早节点
{ // 即u是当前SCC的根节点（发现时间最早）
rt[u] = u; // 将u标记为自身SCC的根
while(stk[top] != u) // 从栈顶弹出节点直到u（包括u）
{
rt[stk[top]] = u; // 这些节点都属于以u为根的SCC
top--;
}
top--; // 弹出u自身
}
}
Kosaraju的板子——更好懂的SCC求解算法
//g2是对于图g反向建边的结果
void dfs1(int u)
{
vis[u] = true;
for (int v : g[u])
if (!vis[v]) dfs1(v);
s.push_back(u);
}
void dfs2(int u)
{
color[u] = sccCnt;
for (int v : g2[u])
if (!color[v]) dfs2(v);
}
void kosaraju()
{
sccCnt = 0;
for (int i = 1; i <= n; ++i)
if (!vis[i]) dfs1(i);
for (int i = n; i >= 1; --i)
if (!color[s[i]])
{ ++sccCnt; dfs2(s[i]); }
}
二、割点与桥
定义
·删掉之后会使得整个图的极大连通分量个数增加的点，叫做割点。
·删掉之后会使得整个图的极大连通分量个数增加的边，叫做桥。
性质
1.Tarjan求割点
如果 \exists 节点 p ，其 DFS 子树内 \exists 节点 q ，有：
low[q] \geq dfn[p]
则 p 是一个割点，因为 q 只能通过 p 达到比 p 的时间戳更小的节点。
例外：如果根节点在 DFS 树上有（至少）两个子节点，那么根节点也是一个割点。
Tarjan求割点的板子
void Tarjan(int u,int father)//doubao说这个有问题，不知道qwq
{
dfn[u] = ++cnt;
low[u] = cnt;
int tot = 0;
for(auto v : E[u])
{
if(!dfn[v])
{
Tarjan(v,u);
low[u] = min(low[u],low[v]);
tot += (low[v] >= dfn[u]);//如上文性质
}
else low[u] = min(low[u],dfn[v]);
}
if(u == father) ise[u] = (tot > 1);
else ise[u] = tot > 0;
}
2.Tarjan求桥
对于边 E(p,q) 来说，如果 p 的子节点是 q ，而 q 的后代通过返祖边只能到达 q ，那么E就是一个桥。类似地，判定方式 ：
low[q] > dfn[p]
Tarjan求桥的板子
void Tarjan(int u,int father)
{
dfn[u] = ++cnt;
low[u] = cnt;
for(auto v : E[u])
{
if(!dfn[v])
{
Tarjan(v,u);
low[u] = min(low[u],low[v]);
if(low[v] > dfn[u])
... //此时边(u,v)即为一座桥，视题目要求加以标记
}
else low[u] = min(low[u],dfn[v]);
}
}
课后练习补充
· 对于任意一个DAG G ，我们记 a，b 分别是 G 中入度为0的点、出度为0的点的数量，若欲使得 G 变为一个强连通图，至少需要添加有向边数量为：
