因ppt太水 遂有此文
有向图
求强连通分量
点击查看代码
void tarjan(int x)
{
dfn[x]=low[x]=++num;
stk.push(x);
f[x]=1;
for(int i=head[x];i;i=net[i])
{
if(!dfn[to[i]])
{
tarjan(to[i]);
low[x]=min(low[x],low[to[i]]);
}
else if(f[to[i]])
{
low[x]=min(low[x],dfn[to[i]]);
}
}
if(low[x]==dfn[x])
{
int y;
++t;
do
{
y=stk.top();
stk.pop();
f[y]=0;
belong[y]=t;
vl[t]+=v[y];
}while(y!=x);
}
}
重建 缩点
点击查看代码
void reb()
{
for(int i=1;i<=n;i++)
{
for(int j=head[i];j;j=net[j])
{
if(belong[i]!=belong[to[j]]) add1(belong[i],belong[to[j]]);
}
}
}
无向图
求割边
点击查看代码
//存边要从2开始存
void tarjan(int x,int in_edge)
{
dfn[x]=low[x]=++num;
for(int i=head[x];i;i=edge[i].next)
{
int y=edge[i].to;
if(!dfn[y])
{
tarjan(y,i);
low[x]=min(low[x],low[y]);
if(low[y]>dfn[x])
{
bridge[i]=bridge[i^1]=1;
}
}
else if(i!=(in_edge^1))
{
low[x]=min(low[x],dfn[y]);
}
}
}
求割点
点击查看代码
void tarjan(int now)
{
dfn[now]=low[now]=++num;
int flag=0;
for(int i=head[now];i;i=edge[i].next)
{
int y=edge[i].to;
if(!dfn[y])
{
tarjan(y);
low[now]=min(low[now],low[y]);
if(low[y]>=dfn[now])
{
flag++;
if(now!=root||flag>1) cut[now]=1;
}
}
else
{
low[now]=min(low[now],dfn[y]);
}
}
}