缩点
Tarjan模板
dfs过程的每条边x→y
-
树枝边（在搜索树中的边，y从未访问过），那么递归处理y；low[x]=min(low[x],low[y])
-
后向边（y被访问过，且在栈中），low[x]=min(low[x],dfn[y])
-
横叉边（y被访问过，但不在栈中），什么也不做
对不同强连通分量重新建图，新图为DAG，在新图里拓扑排序+DP求最长链
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int maxn=400005,maxm=4000005;
queue<int> q;
int top=-1,num,scc_num,n,m,w[maxn],w_c[maxn],ans,dfn[maxn],
low[maxn],stack[maxn],c[maxn],f[maxn],du[maxn];
bool vis[maxn];
struct data{//存储边 便于建新图
int from,to;
}node[maxn];
struct edge{
#define New(p) p=&e[++top]
int to;edge *Nex;
}*head[maxn],e[maxm];
inline void add(int x,int y){
edge *p;New(p);p->to=y;p->Nex=head[x];head[x]=p;
}
void tarjan(int x){
dfn[x]=low[x]=++num;
stack[++top]=x;vis[x]=true;
for(edge *i=head[x];i!=NULL;i=i->Nex){
if(!dfn[i->to]){//树枝边
tarjan(i->to);
low[x]=min(low[x],low[i->to]);
}
else if(vis[i->to]){//返祖边
low[x]=min(low[x],dfn[i->to]);
}
}
if(dfn[x]==low[x]){//找到SCC
++scc_num;
while(int tmp=stack[top--]){
vis[tmp]=false;
c[tmp]=scc_num;
w_c[scc_num]+=w[tmp];//更新新图点权
if(x==tmp) break;
}
}
}
void my_clear(){
memset(e,0,sizeof(e));
memset(head,0,sizeof(head));
top=-1;
}
void topo(){
for(int i=1;i<=scc_num;++i) if(!du[i]){
q.push(i);
f[i]=w_c[i];//入度为0时初始化为该点点权
}
while(!q.empty()){
int h=q.front();q.pop();
for(edge *i=head[h];i!=NULL;i=i->Nex){
f[i->to]=max(f[i->to],f[h]+w_c[i->to]);//简单DP
--du[i->to];
if(!du[i->to]) q.push(i->to);
}
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i) scanf("%d",&w[i]);
for(int i=1,x,y;i<=m;++i){
scanf("%d%d",&x,&y);
add(x,y);
node[i].from=x;
node[i].to=y;
}
for(int i=1;i<=n;++i) if(!dfn[i]) tarjan(i);
my_clear();//清空原图
for(int i=1;i<=m;++i){
if(c[node[i].from] != c[node[i].to]){//对原来每条边 若连接的两点不在同一SCC
add(c[node[i].from],c[node[i].to]);//建边 （方向不变）
++du[c[node[i].to]];//++入度
}
}
topo();//拓扑排序
for(int i=1;i<=scc_num;++i) ans=max(ans,f[i]);
printf("%d",ans);
return 0;
}