tarjan 全家桶
- 关于tarjan 它太强了 CCCOrz
dfs树&low
- dfs树：在图上做不重复经过同一点的dfs，经过的边与点形成一棵树。于是图上所有点都被这棵树包含，一部分边被包含。称被包含的点叫树边，其他边叫回边。整个图就是dfs树，由于是由dfs得到。所以dfs树有非常强的性质，所有回边一定是从一点开始，到它的一个祖先，也就是说两棵没有交集的子树之间一定没有边相连。
- dfn：dfn[now]表示now点的dfn序。
- low：在做tarjan算法时通常需要开一个low数组，low的定义在处理不同问题时可能略有区别。大体为low[rt]表示以rt为根的子树中经过树边和一条回边能到达的dfn最小的点的dfn。
其实理解tarjan的最好办法就是感性
强连通分量
void tarjan(int now)
{
dfn[now]=low[now]=++tot;
s.push(now);in[now]=1;
for(int i=head[now];i;i=nxt[i])
{
if(!dfn[to[i]])
tarjan(to[i]),low[now]=min(low[to[i]],low[now]);
else if(in[to[i]])
low[now]=min(dfn[to[i]],low[now]);
}
if(low[now]==dfn[now])
{
color++;
while(in[now])
{
in[s.top()]=0;
col[s.top()]=color;
ac[color]+=a[s.top()];
s.pop();
}
}
}
割点
void tarjan(int now,int fa)
{
low[now]=dfn[now]=++cnt;
int son=0;
for(int i=head[now];i;i=nxt[i])
{
int v=to[i];
if(!dfn[v])
{
tarjan(v,now);
low[now]=min(low[now],low[v]);
if(low[v]>=dfn[now]&&fa!=now)
is[now]=1;
son++;
}
else low[now]=min(low[now],dfn[v]);
}
if(fa==now&&son>=2)
is[now]=1;
}
双连通分量（圆方树）
void tarjan(int now)///建立圆方树
{
dfn[now]=low[now]=++dfc;
stk[++tp]=now;
++tot;
for(int i=0;i
Original: https://www.cnblogs.com/29taorz/p/15785163.html
Author: T_X蒻
Title: tarjan全家桶
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/584309/
转载文章受原作者版权保护。转载请注明原作者出处！