P3387 【模板】缩点

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
const int N = 1e4 + 1 ;
int n , m ;
vector < int > to [ N ] ;
int val [ N ] ;
void add ( int x , int y ) {
    to [ x ] . push_back ( y ) ;
}
int dfn [ N ] , low [ N ] , cnt ;
int a [ N ] , num [ N ] ;
int st [ N ] , top , co [ N ] , color ;
void Tarjan ( int x ) {
    dfn [ x ] = low [ x ] = ++ cnt;
    st [ ++ top ] = x;
    for ( auto y : to [ x ] ) {
        if ( ! dfn [ y ] )
            Tarjan ( y ),
            low [ x ] = min ( low [ x ] , low [ y ] ) ;
        else
            if ( ! co [ y ] )
            low [ x ] = min ( low [ x ] , dfn [ y ] ) ;
    }
    if ( low [ x ] == dfn [ x ] ) {
        color ++;
        while ( top && st [ top ] != x )
            co [ st [ top -- ] ] = color;
        co [ st [ top -- ] ] = color;
    }
    return;
}
vector < int > ex [ N ] ;
int in [ N ] , dist [ N ] , vis [ N ] , ans;
int main ( ) {
    cin >> n >> m;
    for ( int i = 1 ; i <= n ; i ++ )
        cin >> a [ i ] ;
    for ( int i = 1 ; i <= m ; i ++ )
    {
        static int x , y;
        cin >> x >> y;
        add ( x , y ) ;
    }
    for ( int i = 1 ; i <= n ; i ++ )
        if ( ! co [ i ] )
        Tarjan ( i ) ;
    for ( int i = 1 ; i <= n ; i ++ )
    {
        num [ co [ i ] ] += a [ i ] ;
        for ( auto j : to [ i ] ) {
            if ( co [ j ] == co [ i ] ) continue;
            ex [ co [ i ] ] . push_back ( co [ j ] ) ;
            in [ co [ j ] ] ++ ;
        }
    }
    deque < int > dq;
    for ( int i = 1 ; i <= color ; i ++ )
        ans = max ( ans , num [ i ] ) ;
    for ( int i = 1 ; i <= color ; i ++ )
        if ( in [ i ] == 0 )
            dq . push_back ( i ),
            dist [ i ] = num [ i ];
    while ( ! dq . empty ( ) ) {
        int x = dq . front ( ) ;
        dq . pop_front ( ) ;
        for ( auto y : ex [ x ] ) {
            if ( dist [ y ] < dist [ x ] + num [ y ] )
            {
                dist [ y ] = dist [ x ]  + num [ y ] ;
                ans = max ( ans , dist [ y ] ) ;
                if ( vis [ y ] == 0 ) dq . push_back ( y ) ;
            }
        }
    }
    cout << ans << endl;
    return 0 ;
}