文章目录
解决问题
Tarjan 算法是图论中非常实用 / 常用的算法之一，能解决强连通分量（有向图两点互达），双连通分量（任意两点存在至少两条”边不重复”的路径的图），割点和桥，求最近公共祖先（LCA）等问题。
求强连通分量（缩点）
一些定义
时间戳
d
f
n
dfn
dfn ：标记图中每个节点在进行深度优先搜索时被访问的时间顺序
追溯值
l
o
w
low
low ：搜索树中
d
f
n
dfn
dfn 最小值
算法思想
处理一个连通分量时，将访问过的节点存入一个栈中
不断
d
f
s
dfs
dfs 进未访问的节点
(
d
f
n
[
y
]
=
=
0
)
(dfn[y]==0)
(dfn[y]==0) ，入栈，向下访问
若节点
y
y
y 未访问过，则向下访问，同时
l
o
w
[
x
]
=
m
i
n
(
l
o
w
[
x
]
,
l
o
w
[
y
]
)
low[x]=min(low[x],low[y])
low[x]=min(low[x],low[y])
若
y
y
y 访问过且在栈
v
i
s
[
y
]
=
1
vis[y]=1
vis[y]=1 中，说明在一个连通分量中，
l
o
w
[
x
]
=
m
i
n
(
l
o
w
[
x
]
,
d
f
n
[
y
]
/
l
o
w
[
y
]
)
low[x]=min(low[x],dfn[y]/low[y])
low[x]=min(low[x],dfn[y]/low[y])，这个
/
/
/ 见下面的求割点
结束后若节点
x
x
x 的
d
f
n
[
x
]
=
=
l
o
w
[
x
]
dfn[x]==low[x]
dfn[x]==low[x]，说明这是以
x
x
x 为根的强连通分量，将栈中节点一直弹出至
x
x
x，同时
v
i
s
=
0
vis=0
vis=0，该强连通分量结束
代码
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int N=1e4+9;
int n,m,tim,cnt,ans;
int a[N],dfn[N],low[N],vis[N],col[N],na[N],r[N],sum[N];
vector<int>e[N],st,ne[N];
queue<int>q;
void tarjan(int x)
{
st.pb(x); vis[x]=1;
dfn[x]=low[x]=++tim;
for(auto y:e[x])
{
if(!dfn[y])
{
tarjan(y);
low[x]=min(low[x],low[y]);
}
else if(vis[y]) low[x]=min(low[x],dfn[y]);
}
if(dfn[x]==low[x])
{
++cnt;
while(1)
{
int y=st.back(); st.pop_back();
col[y]=cnt; vis[y]=0;
na[cnt]+=a[y];
if(y==x) break;
}
}
}
void topo()
{
for(int i=1;i<=cnt;i++)
{
sum[i]=na[i];
if(!r[i]) q.push(i);
}
while(q.size())
{
int x=q.front(); q.pop();
for(auto y:ne[x])
{
sum[y]=max(sum[y],sum[x]+na[y]);
r[y]--;
if(!r[y]) q.push(y);
}
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
e[x].pb(y);
}
for(int i=1;i<=n;i++)
if(!dfn[i])
tarjan(i);
for(int i=1;i<=n;i++)
for(auto j:e[i])
if(col[i]!=col[j])
ne[col[i]].pb(col[j]),r[col[j]]++;
topo();
for(int i=1;i<=cnt;i++)
ans=max(ans,sum[i]);
printf("%d\n",ans);
return 0;
}
割点
算法思想
首先选定一个根节点，从该根节点开始遍历整个图（使用
d
f
s
dfs
dfs ）。
对于根节点，判断是不是割点很简单——计算其子树数量，如果有
2
2
2 棵即以上的子树，就是割点。
对于非根节点，对于边
(
u
,
v
)
(u, v)
(u,v)，如果
d
f
n
[
u
]
≤
l
o
w
[
v
]
dfn[u]≤low[v]
dfn[u]≤low[v]，此式子表明节点
v
v
v 后面没有边重新回到节点
u
u
u 所在的连通分量，此时
u
u
u 就是割点。
同时需要注意的是
l
o
w
[
x
]
=
m
i
n
(
l
o
w
[
x
]
,
d
f
n
[
y
]
)
low[x]=min(low[x],dfn[y])
low[x]=min(low[x],dfn[y])，而不能
l
o
w
[
x
]
=
m
i
n
(
l
o
w
[
x
]
,
l
o
w
[
y
]
)
low[x]=min(low[x],low[y])
low[x]=min(low[x],low[y])。
对
l
o
w
[
x
]
=
m
i
n
(
l
o
w
[
x
]
,
d
f
n
[
y
]
)
low[x]=min(low[x],dfn[y])
low[x]=min(low[x],dfn[y]) 的理解
在求强连通分量时，如果
y
y
y 已经在栈中，那么说明
x
，
y
x，y
x，y 一定在同一个强连通分量中，所以到最后
l
o
w
[
x
]
=
l
o
w
[
y
]
low[x]=low[y]
low[x]=low[y] 是必然的，提前更新也不会有问题。
但是在求割点时，
l
o
w
low
low 的定义有了小小的变化，不再是最早能追溯到的祖先，（因为是个无向图）没有意义，应该是最早能绕到的割点。
为什么用绕到，是因为是无向边，所以有另一条路可以走，如果把
d
f
n
[
y
]
dfn[y]
dfn[y] 改成
l
o
w
[
y
]
low[y]
low[y] 就会上翻过头，可能翻进另一个环中
例如：
显然对节点
7
7
7，其
l
o
w
low
low 不能等于
l
o
w
[
4
]
low[4]
low[4]，因为对右边的分量来讲，是从节点
4
4
4 进入这个分量的，能绕回最早的已访问过的节点仍然是
4
4
4，不能从其他边进入左边的分量，对
4
4
4 来说它就是割点
所以
l
o
w
[
x
]
=
m
i
n
(
l
o
w
[
x
]
,
d
f
n
[
y
]
)
low[x]=min(low[x],dfn[y])
low[x]=min(low[x],dfn[y])
代码
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int N=2e4+9;
int n,m,tim,ans;
int dfn[N],low[N],gd[N];
vector<int>e[N];
void tarjan(int x,int fa,int rt)
{
int st=0;
dfn[x]=low[x]=++tim;
for(auto y:e[x])
{
if(y==fa) continue;
if(!dfn[y])
{
tarjan(y,x,rt); st++;
low[x]=min(low[x],low[y]);
if((dfn[x]<=low[y]&&x!=rt)||(x==rt&&st>1)) gd[x]=1;
}
else low[x]=min(low[x],dfn[y]);
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
e[x].pb(y); e[y].pb(x);
}
for(int i=1;i<=n;i++)
if(!dfn[i])
tarjan(i,0,i);
for(int i=1;i<=n;i++)
ans+=gd[i];
printf("%d\n",ans);
for(int i=1;i<=n;i++)
if(gd[i])
printf("%d ",i);
return 0;
}
桥
判断条件
对于边
<
x
,
y
>
<x,y>
<x,y>，只要满足
d
f
n
[
x
]
<
l
o
w
[
y
]
dfn[x]<low[y]
dfn[x]<low[y] 就证明这条边是一个桥。
为什么呢？根据两个数组的定义，
d
f
n
[
x
]
<
l
o
w
[
y
]
dfn[x]<low[y]
dfn[x]<low[y] 说明了
y
y
y 点在不通过
<
x
,
y
>
<x, y>
<x,y> 这条边的情况下，是无论如何也无法到达
x
x
x 点的。所以这两个点一定在两个分量里面，因此他们俩的边一定是一个桥。