visitingfriend.cpp

#include<bits/stdc++.h>
using namespace std;
#define mx 100005
vector<int>g[mx],rg[mx],sg[mx];
int visited[mx];
long long cost[mx],cost1[mx];
long long scc[mx];
long long ans[mx];
stack<int>s;
int co=1;
void dfs1(int src)
{
    visited[src]=1;
    for(auto v:g[src])
    {
        if(visited[v]==0)
        {
            dfs1(v);
        }
    }
    s.push(src);
}
void dfs2(int src)
{
    visited[src]=1;
    scc[src]=co;
    cost1[co]+=cost[src];
    for(auto v:rg[src])
    {
        if(visited[v]==0)
        {
            dfs2(v);
        }
    }
 
}
void dfs3(int src)
{
    visited[src]=1;
    for(auto v:sg[src])
    {
        if(visited[v]==0)
        {
            dfs3(v);
        }
    }
    s.push(src);
}
 
 
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; i++)
    {
        scanf("%lld",&cost[i]);
    }
    for(int i=0; i<m; i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        g[x].push_back(y);
        rg[y].push_back(x);
    }
    for(int i=1; i<=n; i++)
    {
        if(visited[i]==0)
        {
            dfs1(i);
        }
    }
    memset(visited,0,sizeof visited);
 
    while(!s.empty())
    {
        int x =s.top();
 
        s.pop();
        if(visited[x]==0)
        {
            dfs2(x);
            co++;
        }
    }
 
    for(int i=1; i<=n; i++)
    {
        for(auto v:g[i])
        {
 
            if(scc[i]!=scc[v])
            {
                sg[scc[i]].push_back(scc[v]);
            }
        }
    }
    for(int i=1; i<co; i++)
    {
        sort(sg[i].begin(), sg[i].end());
 
        auto iter = std::unique(sg[i].begin(), sg[i].end());
 
        sg[i].erase(iter, sg[i].end());
    }
    memset(visited,0,sizeof visited);
    for(int i=1; i<co; i++)
    {
        if(visited[i]==0)
        {
            dfs3(i);
        }
 
    };
    vector<int>rev;
    while(!s.empty())
    {
        rev.push_back(s.top());
        s.pop();
    }
    reverse(rev.begin(),rev.end());
 
 
 
    for(int i=1; i<co; i++)
    {
        int v=rev[i-1];
        //cout<<v<<endl;
 
 
        for(auto i: sg[v] ) ans[v] = max(ans[v], ans[i]);
 
        ans[v] += cost1[v];
 
    }
    for(int i=1; i<=n; i++)
    {
 
        printf("%lld ",ans[scc[i]]);
    }
    cout<<endl;
 
 
 
 
}