Cod sursă (job #816448)

#include <bits/stdc++.h>
using namespace std;

const int NMAX = 1e5;

FILE *fin, *fout;

int n, m, h;
vector<int> graph[NMAX], revGraph[NMAX], stackOrder, strongComp[NMAX];
bool vis[NMAX];
int comp[NMAX];
int val[NMAX];
int valComp[NMAX];
int ansComp[NMAX];

int indeg[NMAX];
set<int> revDag[NMAX];
vector<int> REVDAG[NMAX];
//set<int> dag[NMAX];
vector<int> topOrder;

void dfs(int node, vector<int>* g, vector<int>& v) {
    vis[node] = true;
    for(auto x : g[node]) {
        if(!vis[x]) {
            dfs(x, g, v);
        }
    }
    v.push_back(node);
}

void sortaret(int node) {
    vis[node] = true;
    for(auto child : REVDAG[node]) {
        if(!vis[child]) {
            sortaret(child);
        }
    }
    topOrder.push_back(node);
}

int getInt() {
    int nr = 0;
    char ch;
    while(!isdigit(ch = fgetc(fin)));
    do {
        nr = nr * 10 + ch - '0';
    } while(isdigit(ch = fgetc(fin)));
    return nr;
}

int main() {
    fin = fopen("risipa.in", "r");
    fout = fopen("risipa.out", "w");
    n = getInt();
    m = getInt();
    h = getInt();
    h--;
    for(int i = 0; i < n; i++)
        val[i] = getInt();
    for(int i = 0; i < m; i++) {
        int a, b;
        a = getInt();
        b = getInt();
        a--, b--;
        graph[a].push_back(b);
        revGraph[b].push_back(a);
    }
    for(int i = 0; i < n; i++) {
        if(!vis[i]) {
            dfs(i, graph, stackOrder);
        }
    }
    for(int i = 0; i < n; i++)
        vis[i] = false;
    int noComp = 0;
    while(!stackOrder.empty()) {
        int node = stackOrder.back();
        stackOrder.pop_back();
        if(!vis[node]) {
            dfs(node, revGraph, strongComp[noComp]);
            noComp++;
        }
    }
    for(int i = 0; i < noComp; i++) {
//        cout << i << " : ";
        for(auto x : strongComp[i]) {
            comp[x] = i;
//            cout << x << ' ';
            valComp[i] += val[x];
        }
//        cout << '\n';
    }
    for(int i = 0; i < n; i++) {
        for(auto y : graph[i]) {
            int xx = comp[i];
            int yy = comp[y];
            if (xx != yy && revDag[yy].find(xx) == revDag[yy].end()) {
//                    dag[xx].insert(yy);
//                    cout << xx << " -- " << yy << '\n';
                revDag[yy].insert(xx);
                REVDAG[yy].push_back(xx);
                indeg[xx]++;
            }
        }
    }
    for(int i = 0; i < noComp; i++)
        vis[i] = false;
    for(int i = 0; i < noComp; i++) {
        if(indeg[i] == 0) {
            sortaret(i);
        }
    }
//    for(auto x : topOrder)
//        cout << x << ' ';
//    cout << '\n';
    int hComp = comp[h];
    ansComp[hComp] = valComp[hComp];
    for(int i = 0; i < noComp; i++) {
        for (auto x: REVDAG[topOrder[i]]) {
            if(ansComp[x] != 0)
                ansComp[topOrder[i]] = max(ansComp[topOrder[i]], ansComp[x] + valComp[topOrder[i]]);
        }
    }
    for(int i = 0; i < n; i++) {
        fprintf(fout, "%d\n", ansComp[comp[i]]);
    }
    return 0;
}

/*
7 8 1
5 3 2 3 4 1 4
4 2
4 6
1 7
2 3
3 7
1 2
3 4
5 4


5
13
13
13
0
14
17

5 5 5
1 2 3 4 5
1 2
2 3
3 4
4 1
5 3
 */