缩点
学了tarjan算法，今天我就简单谈谈我对其的理解吧；
废话不多说先上一道题(洛谷P3387)，又是一道模板题，对吧(会的大佬勿喷)； 题目背景
缩点+DP
题目描述
给定一个n个点m条边有向图，每个点有一个权值，求一条路径，使路径经过的点权值之和最大。你只需要求出这个权值和。
允许多次经过一条边或者一个点，但是，重复经过的点，权值只计算一次。
这道题怎么做(我放在这里当然是用tarjan了)，可能有其他的方法但今天讲tarjan算法那我们就主讲它吧；
tarjan算法的主要思想就是将互相间可以到达的点(及环)缩成一个点，然后就会构成一个有向无环图，对于有向无环图(因为其具有很多优良的性质)便可以进行DP，或者其它一些操作；
下面我就来讲一下怎么将一些可以互相到达的点缩成一个点； 其中用黄圈 圈起来的点便可以缩成一个点(及把它们强联通)；
那怎么求点之间是否强联通呢？我们可以先随便找一个点对它进行dsf，我们用一个数组dfn来记录它被dfs时的顺序；
我们从1号点开始dfs图上的序号便是dfn，我们再用一个low数组来记录本号节点最早可以到达的点的dfn，我们可以发现当一个点的low小于它自己的low时，它便可以到达其他点，这是就能形成环。如上图，我们dfs到了7，发现还可以到5所以四的low便被更新为5，这个很容易看出来是强连通的，但左侧的并不是前联通的，我们就应该开一个栈来记录。那么便会出现下面几种情况：
子节点(v)已访问过,并且在栈里非常显然,该节点(u)可以回到他的某一祖宗(v)处,从祖宗节点(v)到该节点(u)中间的所有节点可以连成环 将该节点(u)的访问时间标记为 重新标记为该环最小的时间(缩点)子节点(v)已访问过。
不在栈里无法连成环,一个节点的两棵子树间的单向边子节点(v)未访问过继续 DFS 遍历该子节点(v) 遍历完该子节点(v)的所有子节点后,尝试缩点将该节点(u)的时间标记 重新标记为该节点(u)与子节点(v)时间标记的最小值(如果需要修改就证明它的 某个后代节点和它的祖宗节点有连接 )
话不多说，上代码
void tarjan(int u)
{
dfn[u]=++dfn[0];
low[u]=dfn[u];//初始化
st[++st[0]]=u;//st是栈
inst[u]=1;//表示在栈里
for(int i=0;i<q[u].size();++i)
{
int v=q[u][i];
if(!dfn[v])//没被遍历过
tarjan(v);
if(inst[v])
low[u]=min(low[v],low[u]);//更新low
}
if(dfn[u]==low[u])//缩点
{
liantong[0]++;
while(st[st[0]]!=u)
{
liantong[st[st[0]]]=liantong[0];
sum[liantong[0]]+=va[st[st[0]]];
inst[st[st[0]]]=0;
st[0]--;
}
liantong[st[st[0]]]=liantong[0];
sum[liantong[0]]+=va[st[st[0]]];
inst[st[st[0]]]=0;
st[0]--;
}
}把这个学会了，其它的就是小意思了，我剩下用的spfa解的这道题，那现在就上全代码吧
#include<bits/stdc++.h>
using namespace std;
vector<int>q[10001];
vector<int>p[10001];
int liantong[100001],va[100001],sum[100001],dfn[100001],low[100001],st[100001];
bool inst[100001],vis[100001];
int x[100001],y[100001],dis[100001],ans;
void tarjan(int u)
{
dfn[u]=++dfn[0];
low[u]=dfn[u];
st[++st[0]]=u;
inst[u]=1;
for(int i=0;i<q[u].size();++i)
{
int v=q[u][i];
if(!dfn[v])
tarjan(v);
if(inst[v])
low[u]=min(low[v],low[u]);
}
if(dfn[u]==low[u])
{
liantong[0]++;
while(st[st[0]]!=u)
{
liantong[st[st[0]]]=liantong[0];
sum[liantong[0]]+=va[st[st[0]]];
inst[st[st[0]]]=0;
st[0]--;
}
liantong[st[st[0]]]=liantong[0];
sum[liantong[0]]+=va[st[st[0]]];
inst[st[st[0]]]=0;
st[0]--;
}
}
void spfa(int x)//蒟蒻的spfa
{
memset(dis,0,sizeof(dis));
memset(vis,0,sizeof(vis));
queue<int>hh;
dis[x]=sum[x];
vis[x]=1;
hh.push(x);
while(!hh.empty())
{
int u=hh.front();
hh.pop();
vis[u]=0;
for(int i=0;i<p[u].size();++i)
{
if(dis[p[u][i]]<dis[u]+sum[p[u][i]])
{
dis[p[u][i]]=dis[u]+sum[p[u][i]];
}
if(!vis[p[u][i]])
{
vis[p[u][i]]=1;
hh.push(p[u][i]);
}
}
}
for(int i=1;i<=liantong[0];++i)
ans=max(ans,dis[i]);
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
scanf("%d",&va[i]);
for(int i=1;i<=m;++i)
{
scanf("%d%d",&x[i],&y[i]);
q[x[i]].push_back(y[i]);
}
for(int i=1;i<=n;++i)
{
if(!dfn[i])
tarjan(i);
}
for(int i=1;i<=m;++i)
{
if(liantong[x[i]]!=liantong[y[i]])
{
p[liantong[x[i]]].push_back(liantong[y[i]]);
}
}
for(int i=1;i<=liantong[0];++i)
spfa(i);
printf("%d",ans);
return 0;
}