#include<bits/stdc++.h> #define ll long long using namespace std; const int N = 2e5 + 10,inf = 0x3f3f3f3f;// g: 原图的邻接表, e: 缩点后新图的邻接表 vector<int> g[N],e[N];// Tarjan算法相关 int dfn[N],low[N],id; // dfn:深度优先序, low:能回溯到的最小dfn, id:时间戳计数器 int q[N],top,inq[N]; // q:模拟栈, top:栈顶, inq:标记节点是否在栈中 int n,m;// 缩点相关 int scc[N],sccnt; // scc[i]:节点i所属的SCC编号, sccnt:SCC计数器 int sccval[N]; // sccval[i]:第i个SCC的总权值// 拓扑排序相关 ll a[N],f[N]; // a[i]:原节点权值, f[i]:以SCC i结尾的最大路径和 int rd[N]; // rd[i]:SCC i的入度// Tarjan算法求强连通分量 void tarjan(int x) {dfn[x] = low[x] = ++id; // 初始化当前节点的dfn和lowq[++top] = x; // 节点入栈inq[x] = 1; // 标记节点在栈中// 遍历所有邻接节点for(int i = 0; i < g[x].size(); i++){int y = g[x][i];if(dfn[y] == 0){ // 树边：y未被访问 tarjan(y);low[x] = min(low[x],low[y]); // 回溯时更新low值 }else if(inq[y]) low[x] = min(low[x],dfn[y]); // 回边：y在栈中 }// 找到SCC的根节点if(low[x] == dfn[x]){sccnt++;while(1){int y = q[top--]; // 弹出栈顶节点inq[y] = 0; // 标记不在栈中scc[y] = sccnt; // 记录节点所属SCCsccval[sccnt] += a[y]; // 累加SCC权值if(x == y) break; // 弹出直到遇到根节点x }} }// 拓扑排序求DAG最长路径,注意拓扑排序中用的是新图e，而非g void topsort() {queue<int> q;ll ans = 0;// 初始化：所有入度为0的SCC入队for(int i = 1; i <= sccnt; i++){ f[i] = sccval[i]; // 初始值为SCC自身权值if(rd[i] == 0) q.push(i); // 入度为0的入队 }// 拓扑排序while(q.size()){int x = q.front(); q.pop();// 遍历x的所有出边for(int i = 0; i < e[x].size(); i++){int y = e[x][i];rd[y]--; // 入度减1// 状态转移：f[y] = max(f[y], f[x] + sccval[y])f[y] = max(f[y],f[x] + sccval[y]);ans = max(ans,f[y]); // 更新答案if(rd[y] == 0) q.push(y); // 入度为0时入队 }}// 确保找到最大值（处理没有入度的孤立SCC）for(int i = 1; i <= sccnt; i++) ans = max(ans,f[i]);cout << ans; }int main() {// 输入处理cin >> n >> m;for(int i = 1; i <= n; i++) cin >> a[i]; // 读入点权for(int i = 1; i <= m; i++){int x,y; cin >> x >> y;g[x].push_back(y); // 构建原图 }// 步骤1: Tarjan算法求所有强连通分量for(int i = 1; i <= n; i++){if(dfn[i] == 0) tarjan(i); // 对每个未访问节点执行Tarjan }// 步骤2: 构建缩点后的新图(DAG)for(int i = 1; i <= n; i++){for(int j = 0; j < g[i].size(); j++){int y = g[i][j];if(scc[i] != scc[y]){ // 不同SCC之间的边e[scc[i]].push_back(scc[y]); // 添加新图的边rd[scc[y]]++; // 目标SCC入度加1 }}}// 步骤3: 拓扑排序求最长路径 topsort();return 0; }