前言
首先你要知道什么是强连通分量再来，不会的话我给你链接啊！
好像上面那个链接已经替代了我 ：)
tarjan
tarjan 这个算法的演示图比较复杂，我推荐看这篇博客，这时你肯定要问了，你都推荐别人的博客了，那我看你干嘛，别急，他没给你代可以给你！
我们用 \(dfn[x]\) 表示点 \(x\) dfs 序（dfs遍历时访问的顺序），我们又用 \(low[x]\) 表示 \(x\) 点可以到达最小的 dfs 序，我们又用栈来储存每个点，当遇到环时为了输出当前的强连通分量。
dfn[x]=low[x]=++t;//dfs序
s[++top]=x;//数组模拟栈
然后我们就枚举出边，如果下一个点没遍历过，递归，更新 low，否则直接更新 low ，
for(int i=head[x];i!=-1;i=edge[i].next){
int y=edge[i].to;
if(dfn[y]==0){
tarjan(y);
low[x]=min(low[x],low[y]);//与那个点的low比较
}
else{
low[x]=min(low[x],dfn[y]);//因为已经又dfn所以直接比较
}
}
如果 \(dfn[x]\) 与 \(low[x]\) 相等，说明找到了强连通分量的根（开始节点），然后我们就输出这个强连通分量就好了。
if(dfn[x]==low[x]){
int b;
do{
b=s[top];
cout<<b<<" ";
}while(x!=s[top--]);
cout<<"\n";
}
完整代码：
void tarjan(int x){
dfn[x]=low[x]=++t;
s[++top]=x;
for(int i=head[x];i!=-1;i=edge[i].next){
int y=edge[i].to;
if(dfn[y]==0){
tarjan(y);
low[x]=min(low[x],low[y]);
}
else{
low[x]=min(low[x],dfn[y]);
}
}
if(dfn[x]==low[x]){
int b;
do{
b=s[top--];
cout<<b<<" ";
if(b==x){
break;
}
}while(x!=b);
cout<<"\n";
}
}
void tarjan(int x){
dfn[x]=low[x]=++t;
s[++top]=x;
vis[x]=1;
for(int i=head[x];i!=-1;i=edge[i].next){
int y=edge[i].to;
if(dfn[y]==0){
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]){
int b;
do{
b=s[top--];
of[b]=x;
vis[b]=0;
if(b==x){
break;
}
val[x]+=val[b];
}while(x!=b);
}
}
这样 tarjan 就学会了吧，如果没有可以多看几篇题解。
缩点
例题 1.洛谷 P3387
学 tarjan 肯定要做这个啊！
我还是太菜，没法直接讲清楚 ：（ 但其实就是 tarjan 缩点后拓扑对路径做 dp 求最大权值和（半天说了个废话）
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+4;
const int M=1e5+5;
int n,m;
inline int read(){
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
return x*f;
}
int cnt=0,sum=0;
struct Edge{
int from,to,next;
}edge[2*M],ed[2*M];
int head[N],h[N];
int in[N];
void add_edge(int u,int v){
edge[cnt].to=v;
edge[cnt].from=u;
edge[cnt].next=head[u];
head[u]=cnt++;
}
void add_edge2(int u,int v){
ed[++sum].next=h[u];
ed[sum].to=v;
ed[sum].from=u;
h[u]=sum;
in[v]++;
}
int t=0,top=0;
int s[N];
int dfn[N];
int vis[N];
int val[N];
int low[N];
int of[N];
void tarjan(int x){
dfn[x]=low[x]=++t;
s[++top]=x;
vis[x]=1;
for(int i=head[x];i!=-1;i=edge[i].next){
int y=edge[i].to;
if(dfn[y]==0){
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]){
int b;
do{
b=s[top--];
of[b]=x;
vis[b]=0;
if(b==x){
break;
}
val[x]+=val[b];
}while(x!=b);
}
}
queue<int> q;
int dis[N];
void topo(){
for(int i=1;i<=n;i++){
if(of[i]==i&&in[i]==0){
q.push(i);
dis[i]=val[i];
}
}
while(!q.empty()){
int k=q.front();
q.pop();
for(int i=h[k];i!=-1;i=ed[i].next){
int v=ed[i].to;
dis[v]=max(dis[v],dis[k]+val[v]);
if(--in[v]==0){
q.push(v);
}
}
}
int ans=0;
for(int i=1;i<=n;i++){
ans=max(ans,dis[i]);
}
cout<<ans;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
n=read(),m=read();
for(int i=1;i<=n;i++){
head[i]=-1;
h[i]=-1;
val[i]=read();
}
for(int i=1;i<=m;i++){
int u,v;
u=read(),v=read();
add_edge(u,v);
}
for(int i=1;i<=n;i++){
if(dfn[i]==0){
tarjan(i);
}
}
for(int i=1;i<=m;i++){
int x=of[edge[i].from],y=of[edge[i].to];
if(x!=y){
add_edge2(x,y);
}
}
topo();
return 0;
}
例题 2.洛谷P3627
就是缩点然后spfa跑找权值最大的终点。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define N 500005
int n,m;
int uu[N],vv[N];
int cnt=0;
struct Edge{
int to,next,w;
}edge[2*N];
int head[N];
void add_edge(int u,int v){
cnt++;
edge[cnt].to=v;
edge[cnt].next=head[u];
head[u]=cnt;
}
void add_edge2(int u,int v,int w){
cnt++;
edge[cnt].to=v;
edge[cnt].w=w;
edge[cnt].next=head[u];
head[u]=cnt;
}
int t=0,top=0,tot=0;
int s[N];
int dfn[N];
int vis[N];
int val[N];
int sum[N];
int low[N];
int of[N];
void tarjan(int x){
dfn[x]=low[x]=++t;
s[++top]=x;
vis[x]=1;
for(int i=head[x];i!=-1;i=edge[i].next){
int y=edge[i].to;
if(dfn[y]==0){
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]){
tot++;
do{
int b=s[top];
sum[tot]+=val[b];
vis[b]=0;
of[b]=tot;
}while(x!=s[top--]);
}
}
queue<int> q;
ll dis[N];
int done[N];
int endd[N];
void spfa(int id){
for(int i=1;i<=tot;i++){
dis[i]=0;
}
int gs=of[id];
q.push(gs);
done[gs]=1;
dis[gs]=sum[gs];
while(!q.empty()){
int e=q.front();
q.pop();
done[e]=0;
for(int i=head[e];i;i=edge[i].next){
int nx=edge[i].to;
if(dis[nx]<dis[e]+edge[i].w){
dis[nx]=dis[e]+edge[i].w;
if(!done[nx]){
q.push(nx);
done[nx]=1;
}
}
}
}
}
int main(){
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=1;i<=n;i++){
head[i]=-1;
}
for(int i=1;i<=m;i++){
cin>>uu[i]>>vv[i];
add_edge(uu[i],vv[i]);
}
for(int i=1;i<=n;i++){
cin>>val[i];
}
int start,ends;
cin>>start>>ends;
for(int i=1;i<=ends;i++){
cin>>endd[i];
}
for(int i=1;i<=n;i++){
if(dfn[i]==0){
tarjan(i);
}
}
cnt=0;
memset(edge,0,sizeof(edge));
memset(head,-1,sizeof(head));
for(int i=1;i<=m;i++){
int x=of[uu[i]],y=of[vv[i]];
if(x!=y){
add_edge2(x,y,sum[y]);
}
}
spfa(start);
ll ans=0;
for(int i=1;i<=ends;i++){
ans=max(ans,dis[of[endd[i]]]);
}
cout<<ans;
return 0;
}