P3387

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n = 0 , m = 0 , cnt = 0 , new_cnt = 0 , dfs_time = 0 , tot = 0;
array<int , 200100> head , dfn , low , instk , belong , val , new_val , new_head , dp , ind;
struct Node{
	int to;
	int nxt;
};
array<Node , 4000100> edge , new_edge;
void new_line(int a , int b)
{
	edge[++ cnt].to = b;
	edge[cnt].nxt = head[a];
	head[a] = cnt;
	return;
}
void new_new_line(int a , int b)
{
	new_edge[++ new_cnt].to = b;
	new_edge[new_cnt].nxt = new_head[a];
	new_head[a] = cnt;
	return;
}
stack<int> s;
queue<int> q;
void tarjan(int x)
{
	s.push(x);
	instk[x] = true;
	dfn[x] = low[x] = ++ dfs_time;
	for(int e = head[x];e;e = edge[e].nxt)
	{
		int to = edge[e].to;
		if(!dfn[to])
		{
			tarjan(to);
			low[x] = min(low[x] , low[to]);
		}
		else if(instk[to])
		{
			low[x] = min(low[x] , dfn[to]);
		}
	}
	if(dfn[x] == low[x])
	{
		int tmp = 0;
		++ tot;
		do{
			tmp = s.top();
			s.pop();
			belong[tmp] = tot;
			new_val[tot] += val[tmp];
			instk[tmp] = false;
		}while(tmp != x);
	}
	return;
}
void link()
{
	for(int i = 1;i <= n;++ i)
	{
		for(int e = head[i];e;e = edge[e].nxt)
		{
			int to = edge[e].to;
			if(belong[i] != belong[to])
			{
				new_new_line(belong[i] , belong[to]);
				++ ind[belong[to]];
			}
		}
	}
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin >> n >> m;
	for(int i = 1;i <= n;++ i)
	{
		cin >> val[i];
	}
	for(int i = 1;i <= m;++ i)
	{
		int x = 0 , y = 0;
		cin >> x >> y;
		new_line(x , y);
		new_line(y , x);
	}
	for(int i = 1;i <= n;++ i)
	{
		if(!dfn[i]) tarjan(i);
	}
	link();
	for(int i = 1;i <= tot;++ i)
	{
		if(!ind[i])
		{
			q.push(i);
			dp[i] = new_val[i];
		}
	}
	while(!q.empty())
	{
		int x = q.front();
		q.pop();
		for(int e = new_head[x];e;e = new_edge[e].nxt)
		{
			int to = new_edge[e].to;
			-- ind[to];
			dp[to] = max(dp[to] , dp[x] + new_val[to]);
			if(!ind[to])
			{
				q.push(to);
			}
		}
	}
	cout << *max_element(dp.data() + 1 , dp.data() + n + 1) << endl;
	return 0;
}

为什么拓扑排序，错了,璇一贯