P3387 【模板】缩点

蒟蒻实在是太弱了，连 tarjan 的板子都调不出来。

求助大佬。

#include<bits/stdc++.h>
#define ll long long
// #define int long long
using namespace std;
const int MAX=1e4+10;
inline int read() {
  int fh = 1, res = 0; char ch = getchar();
  for(; !isdigit(ch); ch = getchar()) if(ch == '-') fh = -1;
  for(; isdigit(ch); ch = getchar()) res = (res << 3) + (res << 1) + (ch ^ '0');
  res = res * fh;
  return res;
}
inline void write(ll x) {
    if(x<0){putchar('-');x=-x;}
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
int top,jl,cnt,w[MAX],dfn[MAX],low[MAX],vis[MAX],sta[MAX],ans,suo[MAX];
int rd[MAX],dis[MAX],n,m;
vector<int> s[MAX];
void tarjan(int u)
{
	low[u]=dfn[u]=++cnt;
	sta[++top]=u;vis[u]=1;
	for(int i=0,siz=s[u].size();i<siz;i++)
	{
		int v=s[u][i];
		if(!dfn[v]){tarjan(v);low[u]=min(low[u],low[v]);}
		else if(vis[v]) low[u]=min(low[u],low[v]);
	}
	if(dfn[u]==low[u])
	{
		vis[u]=0;
		while(sta[top]!=u)
		{
			suo[sta[top]]=u;
			w[u]+=sta[top];
			vis[sta[top--]]=1;
		}
		top--;
	}
	return ;
}
void tuopu()
{
	queue<int> q;
	for(int i=1;i<=n;i++)
		if(rd[i]==0)
			q.push(i);
	while(!q.empty())
	{
		int ff=q.front();
		q.pop();
		for(int i=0,siz=s[ff].size();i<siz;i++)
		{
			int v=s[ff][i];
			dis[v]=max(dis[v],dis[ff]+w[v]);rd[v]--;
			if(rd[v]==0)q.push(v);
		}
	}
	for(int i=1;i<=n;i++) ans=max(ans,dis[suo[i]]);
	return ;
}
int main()
{
	n=read();m=read();
	for(int i=1;i<=n;i++) w[i]=read();
	for(int i=1;i<=m;i++)
	{
		int u=read(),v=read();
		s[u].push_back(v);
//		rd[v]++;
	}
	for(int i=1;i<=m;i++) if(!dfn[i]) tarjan(i);
	for(int i=1;i<=n;i++)
		for(int j=0,siz=s[i].size();j<siz;j++)
		{
			s[i][j]=suo[s[i][j]];
			rd[s[i][j]]++;
		}
	tuopu();
	cout<<ans;
	return 0;
}