P3387 【模板】缩点

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
int n,m,dfn[10010],low[10010],cnt,sccno[10010],cntsccno,indeg[10010];//indeg[]表示缩图各个点的入度 
ull a[10010],a2[10010],dp[10010],ans;//a2[]表示缩图的点权 
vector<int> g[10010],g2[10010];
stack<int> s;
bool instack[10010];
queue<int> q;
void tarjan(int u,int fa) {
	low[u] = dfn[u] = ++cnt;
	s.push(u);
	instack[u] = true;
	for (int i = 0;i < g[u].size();i ++) {
		int v = g[u][i];
		if (!dfn[v]) {
			tarjan(v,u);
			low[u] = min(low[u],low[v]);
		} else if (instack[v]) low[u] = min(low[u],dfn[v]);
	}
	if (low[u] == dfn[u]) {
		++ cntsccno;
		while (s.top() != u) {
			sccno[s.top()] = cntsccno;
			a2[cntsccno] += a[s.top()];//缩图点权 
			s.pop();
		}
		sccno[s.top()] = cntsccno;
		a2[cntsccno] += a[s.top()];//缩图点权 
		s.pop();
	}
	return;
}
void build_g2() {//建缩图 
	for (int i = 1;i <= n;i ++)
		for (int j = 0;j < g[i].size();j ++) {
			int v = g[i][j];
			if (sccno[i] != sccno[j]) {
				g2[sccno[i]].push_back(sccno[v]);//注意要是sccno[i]和sccno[v] 
				++ indeg[sccno[v]];//记入度 
			}
		}
	return;
}
void toposort() {
	for (int i = 1;i <= cntsccno;i ++) {//注意是cntsccno而不是n 
		if (!indeg[i]) {
			q.push(i);
			dp[i] = a2[i];//dp
		}
	}
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		for (int i = 0;i < g2[u].size();i ++) {
			int v = g2[u][i];
			-- indeg[v];
			dp[v] = max(dp[v],dp[u] + a2[v]);//dp
			if (!indeg[v]) {
				q.push(v);
			}
		}
	}
	
	//ans
	ans = 0;
	for (int i = 1;i <= n;i ++)//注意是cntsccno而不是n 
		ans = max(ans,dp[i]);
	return;
}
int main() {
	scanf("%d%d",&n,&m);
	for (int i = 1;i <= n;i ++)
		scanf("%llu",&a[i]);
	for (int i = 1;i <= m;i ++) {
		int ut,vt;
		scanf("%d%d",&ut,&vt);
		g[ut].push_back(vt);
	}
	for (int i = 1;i <= n;i ++)
		if (!dfn[i]) tarjan(i,0);
	build_g2();
	toposort();
	printf("%llu\n",ans);
	return 0;
}