#include<bits/stdc++.h>
using namespace std;
int n,m;
struct edge{ //定义存边的变量
int from,to,next;
} e[10005];
int head[10005];
int cnt;
void Insert(int x,int y){ //链式前向星存边
e[++cnt].from=x;
e[cnt].to=y;
e[cnt].next=head[x];
head[x]=cnt;
}
int dfn[10005]; //上文提到的dfn
int low[10005]; //上文提到的low
int t; //当前搜索的时间，用于给时间戳dfn与low赋初始值
stack<int> s;
int p[100005]; //判断某个元素在不在栈里面
// int tot;
// int color[100005];
void Tarjan(int now){
s.push(now); //讲当前元素放入栈
dfn[now]=low[now]=++t; //讲当前搜索的时间，也就是当前搜过了几个点的数量赋值给时间戳dfn,同时对low进行初始化
p[s.top()]=true;
for(int i=head[now];i;i=e[i].next){ //链式前向星遍历所有节点
int get=e[i].to;
if(!dfn[get]){ //判断当前节点有没有被搜索过
Tarjan(get); //如果没有，那就搜这个节点
low[now]=min(low[now],low[get]); //更新当前节点的low，为什么不是 low[now]=min(low[now],dfn[get]); 呢？我们不妨观察一下，low的值是不是永远≤dfn的？此时既然now可以到达get，那么now自然也可以到达get节点能到达的节点
}
else if(p[get]) low[now]=min(low[now],dfn[get]); //否则判断当前节点在不在栈里，如果不在，就不用理他，如果在那么就可以更新一下当前节点，因为当前节点可以到达get,但此时的low不一定是最终得到的值,所以不能写low[now]=min(low[now],low[get]);
}
if(dfn[now]==low[now]){ //如果两个相等，说明当前节点不能再更新了，不能再找到比自己low更小的值
// tot++;
while(s.top()!=now){ //将栈首到当前元素的所有值弹出队列，说明这堆东西就是一个强连通分量
printf("%d ",s.top());
// color[s.top]=tot;
p[s.top()]=false; //标记其不在栈里
s.pop();
}
printf("%d",s.top()); //因为只是弹到当前节点，当前节点也是包含在这个强连通分量内的，所以再做一次
// color[s.top]=tot;
p[s.top()]=false;
s.pop();
printf("\n");
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int x,y;
scanf("%d%d",&x,&y);
Insert(x,y); //存边
}
for(int i=1;i<=n;i++) //因为图不一定保证是连通的，有可能某个节点不被其他任何节点到达，所以要用for判断一遍如果没有被搜过就搜，搜过了就没他什么事了
if(!dfn[i])
Tarjan(i);
return 0;
}
#include<bits/stdc++.h>
#define MAXN 100005
using namespace std;
long long n,m;
struct edge{
long long from,to,next;
} e[MAXN];
long long head[MAXN];
long long cnt;
long long qlt;
void Insert(long long x,long long y){
e[++cnt].from=x;
e[cnt].to=y;
e[cnt].next=head[x];
head[x]=cnt;
}
long long dfn[MAXN];
long long low[MAXN];
long long t;
stack<int> s;
long long p[MAXN];
long long color[MAXN];
long long f[MAXN];
long long u[MAXN],v[MAXN],l[MAXN];
long long dis[MAXN];
long long mmax;
const long long oo=0x7f7f7f;
void Tarjan(long long now){
s.push(now);
dfn[now]=low[now]=++t;
p[now]=false;
for(long long i=head[now];i;i=e[i].next){
long long get=e[i].to;
if(!dfn[get]){
Tarjan(get);
low[now]=min(low[now],low[get]);
}
else if(!p[get]) low[now]=min(low[now],dfn[get]);
}
if(dfn[now]==low[now]){
qlt++;
while(s.top()!=now){
color[s.top()]=qlt;
p[s.top()]=true;
f[qlt]+=l[s.top()]; //存储缩点后单点的点权
s.pop();
}
color[s.top()]=qlt;
p[s.top()]=true;
f[qlt]+=l[s.top()]; //同上，再做一次
s.pop();
}
}
void dfs(long long now) { //做一遍记忆化搜索来更新从某一个节点的答案
dis[now]=f[now]; //初始化，自己的点权就是自己
long long mmmax=0;
for(long long i=head[now];i;i=e[i].next){ //遍历每个节点
long long get=e[i].to;
if(!dis[get])dfs(get); //如果节点没被搜过就搜
mmmax=max(mmmax,dis[get]); //更新最大值
}
dis[now]+=mmmax; //更新当前值
}
int main(){
scanf("%lld%lld",&n,&m);
for(long long i=1;i<=n;i++) scanf("%lld",&l[i]);
for(long long i=1;i<=m;i++){
scanf("%lld%lld",&u[i],&v[i]);
Insert(u[i],v[i]);
}
for(long long i=1;i<=n;i++)
if(!dfn[i])
Tarjan(i);
memset(e,0,sizeof(e)); //清零重新建图
memset(head,0,sizeof(head));
cnt=0;
for(long long i=1;i<=m;i++)
if(color[u[i]]!=color[v[i]]) //建立缩点后的图，如果两点不在同一个强连通分量里，说明两个集合不连通，所以将其连通
Insert(color[u[i]],color[v[i]]);
for(long long i=1;i<=qlt;i++)
if(!dis[i]){
dfs(i); //如果当前节点没被搜过，就进行记忆化搜索
mmax=max(dis[i],mmax); //更新最大值
}
printf("%lld\n",mmax); //输出答案
return 0;
}
原文：https://www.cnblogs.com/BiuBiu-Miku/p/13382219.html