【ybt】【图论强连通课过例1】有向图缩点

本文主要是介绍【ybt】【图论强连通课过例1】有向图缩点，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

有向图缩点

题目链接：有向图缩点

题目描述

在这里插入图片描述

解题思路

强连通分量模板，用 $T a r j a n$ 算法。

code

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;queue<int> q;int n,m;
int ans;
int tm,tt;
int a[10010];
int v[10010];
int f[10010];
int du[10010];
int dfn[10010];
int low[10010];
int num[10010];
int dui[10010],tp;
int hd[10010],tot;
int hd1[10010],tot1;struct abc{int to,next;
}b[100010],b1[100010];void add(int x,int y)
{b[++tot]=(abc){y,hd[x]};hd[x]=tot;
}void add1(int x,int y)
{b1[++tot1]=(abc){y,hd1[x]};hd1[x]=tot1;
}void tarjan(int x)
{dfn[x]=low[x]=++tm;dui[++tp]=x;for(int i=hd[x];i;i=b[i].next){int y=b[i].to;if(!dfn[y]){tarjan(y);low[x]=min(low[x],low[y]);}else if(!v[y])low[x]=min(low[x],low[y]);}if(dfn[x]==low[x]){v[x]=++tt;num[tt]+=a[x];while(dui[tp]!=x)num[tt]+=a[dui[tp]],v[dui[tp--]]=tt;tp--;}
}void dp()
{for(int i=1;i<=n;i++)if(!du[i])q.push(i),f[i]=num[i];while(!q.empty()){int x=q.front();q.pop();for(int i=hd1[x];i;i=b1[i].next){int y=b1[i].to;f[y]=max(f[y],f[x]+num[y]);du[y]--;if(!du[y])q.push(y);}}
}int main()
{cin>>n>>m;for(int i=1;i<=n;i++)scanf("%d",&a[i]);for(int i=1;i<=m;i++){int x,y;scanf("%d%d",&x,&y);add(x,y);}for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);for(int i=1;i<=n;i++)for(int j=hd[i];j;j=b[j].next){int y=b[j].to;if(v[i]!=v[y]){add1(v[i],v[y]);du[v[y]]++;}}dp();for(int i=1;i<=n;i++)ans=max(ans,f[i]);cout<<ans<<endl;
}