反过来调过去,我还是感觉没学明白缩点
- 讲一个有向图中的所有强连通分量缩成一个点后,构成的新图是一个DAG。
- 一个点所在的强连通分量一定被该点所在DFS搜索树所包含
- 树上的边大致分为:树枝边,前向边(从上往下指),后向边(从下往上指),横叉变。其中前向边肉眼可见地没什么卵用
接下来开始算法流程。
- tarjan的精髓如上次所说,在于DFS搜索树,在DFS搜索树中强连通分量以怎样形式存在是关键问题。对于x,存在祖宗y,从x出发可经过横叉边,返祖边,后向边到达y,则x,y属于同一强连通分量。操作中记录最小 y 为:low(x)=dfn(y)。(其中单点也算强连通块)如果有一个dfn_x=low_x ,那么就是说 x 在一个新的强连通块里,同理,low_x的初始也就是dfn_x。
- 我们用一个栈来维护 已经被遍历过的、还未确定隶属哪个强连通分量的 点,在该栈中越靠栈顶DFS序越靠后(是栈底元素的后代)。
- 关于low_x的求法、更新。考虑如何求low_x:low_x 可能被更新,当且仅当x连出了一条树枝边,横叉边或后向边。设该边连向点 v
1. 树枝边: low_x= min(low_x,low_v) v 到达的点x一定可以到达,且v与x有祖宗关系
2. 后向边: low_x= min(low_x,low_v) v 的祖先一定是 x 的祖先
3. 横叉边:此时分两种情况考虑的
当 v 点已经退栈时,那么点v可到达的DFS序最小的祖先不是x的祖先,对 low_x 没有贡献; 当点v还在栈中时,v 点可到达的DFS序最小的祖先是x的祖先,有 low_x=min(low_x,low_v) (点v可到达的DFS序最小的祖先一定是x的,v 点能到达的点,x一定能到达) 特别地,由于前向边的更新对于求强连分量没有帮(更新是重复的),所以我们也可以有 low_x=min(low_x,low_v)
那么我们只需判断点 x 连出的边是哪一条就可以转移了。显然,当 dfn_v=0 时(此时v未被访问过),这是一条树枝边。我们再维护一个 col 数组, col_i 表示点 i 所在的强连通分量,在点 i 退栈时,我们对col进行赋值,那么当 dfn_v≠0&&col_v=0 时,点v一定在栈中(后向边指向的点一定在栈中,横叉边指向的点满足此条件时在栈中,而前向边是否存在与答案无关),此时用 low_x=min(low_x,low_v) 转移即可,否则无需转移。该算法时间复杂度为(n+m),因为深度优先遍历每个点只会经过一次,每条边也只会访问一次,而每个点都只会进/出栈一次,所以总时间复杂度为(n+m)
//把一个点当成根提溜出来,抖搂抖搂成一棵树
void dfs(int u)
{
//记录dfs序
//可通过任意多dfs边与最多一条非树返祖边到达的、本强连通分量内最小点
dfn[u]=low[u]=++dfs_clock;
s.push(u);
for(int v:g[u])
{
if(!dfn[v])//树边
{
dfs(v);
low[u]=min(low[u],low[v]);
}
else if(!sccnum[v])//返祖
low[u]=min(low[u],dfn[v]);
}
if(low[u]==dfn[u])
{
scccnt++;//强连通块+1
while(1)
{
int x=s.top();
s.pop();
sccnum[x]=scccnt;
sccsz[scccnt]++;
if(x==u) break;
}
}
}
#include<bits/stdc++.h>
using namespace std;
#define N 100010
int n,m,k,tot,top,dfs_clock,ans;
int u[N],v[N],st[N],sum[N],head[N],ac[N],dfn[N],low[N],col[N],into[N],f[N];
struct tree{ int v,next; } a[N];
void add(int x,int y)
{
a[++k].v=y;
a[k].next=head[x];
head[x]=k;
}
void tarjan(int x)
{
dfn[x]=low[x]=++dfs_clock;
st[++top]=x;
for(int i=head[x];i;i=a[i].next)
{
if(!dfn[a[i].v])
{
tarjan(a[i].v);
low[x]=min(low[x],low[a[i].v]);
}
else if(!col[a[i].v]) low[x]=min(low[x],low[a[i].v]);
}
if(dfn[x]==low[x])
{
col[x]=++tot;
sum[tot]+=ac[x];
while(st[top]!=x)
{
sum[tot]+=ac[st[top]];
col[st[top--]]=tot;
}
top--;
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&ac[i]);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&u[i],&v[i]);
add(u[i],v[i]);
}
for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);
memset(head,0 ,sizeof(head));
memset(a,0,sizeof(a));
k=0;
for(int i=1;i<=m;i++)
{
if(col[u[i]]!=col[v[i]])
{
add(col[u[i]],col[v[i]]);
into[col[v[i]]]++;
}
}
queue<int>q;
for(int i=1;i<=tot;i++)
{
f[i]=sum[i];
if(!into[i])q.push(i);
}
while(!q.empty())
{
int y=q.front();
q.pop();
for(int i=head[y];i;i=a[i].next)
{
int x=a[i].v;
f[x]=max(f[x],f[y]+sum[x]);
into[x]--;
if(!into[x]) q.push(x);
}
}
for(int i=1;i<=tot;i++) ans=max(ans,f[i]);
printf("%d",ans);
return 0;
}