Cod sursă (job #816478)

#include <bits/stdc++.h>

using namespace std;
#define MAXN 100000
#define MAXM 300000
int v[MAXN + 1], v1[MAXM], v2[MAXM], low[MAXN + 1], vtime[MAXN + 1], st[MAXN + 1], comp[MAXN + 1], sum[MAXN + 1], dp[MAXN + 1];
char f[MAXN + 1];//1 daca e pe stiva
vector<int> adj[MAXN + 1];
vector<int> adj2[MAXN + 1];
int time1, vf, nrc;
void popScc(int nod) {
    nrc++;
    do {
        vf--;
        sum[nrc] += v[st[vf]];
        comp[st[vf]] = nrc;
        f[st[vf]] = 0;
    } while (st[vf] != nod);
}
void tarjan(int nod) {
    int nr, i, x;
    time1++;
    vtime[nod] = low[nod] = time1;
    st[vf] = nod;
    f[nod] = 1;
    vf++;
    nr = adj[nod].size();
    for (i = 0; i < nr; i++) {
        x = adj[nod][i];
        if (vtime[x] == 0) {
            tarjan(x);
            low[nod] = min(low[nod], low[x]);
        } else if (f[x] > 0) {
            //e pe stiva
            low[nod] = min(low[nod], vtime[x]);
        }
    }
    if (low[nod] == vtime[nod]) {
        popScc(nod);
    }
}
int main()
{
    FILE *fin, *fout;
    //conexitate cu tarjan si dp pe comp sortate topologic
    int n, m, h, i, j, nr, maxs, x;
    fin = fopen("risipa.in", "r");
    fscanf(fin, "%d%d%d", &n, &m, &h);
    for (i = 1; i <= n; i++) {
        fscanf(fin, "%d", &v[i]);
    }
    for (i = 0; i < m; i++) {
        fscanf(fin, "%d%d", &v1[i], &v2[i]);
        adj[v1[i]].push_back(v2[i]);
    }
    fclose(fin);
    tarjan(h);
    //sunt invers topologic, adica cea mai mare componenta ar trebui sa fie prima
    for (i = 0; i < m; i++) {
        if (comp[v1[i]] > 0 && comp[v2[i]] > 0) {
            adj2[comp[v2[i]]].push_back(comp[v1[i]]);//ii pun parintii in vector
        }
    }

    //comp[h] = nrc
    for (i = nrc; i > 0; i--) {
        nr = adj2[i].size();
        maxs = 0;
        for (j = 0; j < nr; j++) {
            x = adj2[i][j];
            if (dp[x] > maxs) {
                maxs = dp[x];
            }
        }

        dp[i] = sum[i] + maxs;
    }
    dp[0] = 0;
    fout = fopen("risipa.out", "w");
    for (i = 1; i <= n; i++) {
        fprintf(fout, "%d\n", dp[comp[i]]);
    }
    fclose(fout);
    return 0;
}