Cod sursă (job #816435)

#include <fstream>
#include <vector>
#include <stack>

using namespace std;

ifstream cin("risipa.in");
ofstream cout("risipa.out");

const int Nmax = 100005;
const int INF = 1e9;

struct nod{
    int numar_componenta, cost;
    vector<int> vecini;

    bool inStiva;
    int timp_descoperit, timp_atins;
    bool vizitat;
};

struct grupa{
    int cost, cost_componenta;
    bool vizitat;
    vector<int> vecini;
};

int n, m, h;
int timp, nr_componente;
nod graf[Nmax];
grupa dag[Nmax];
vector<int> topo_sort;
stack<int> st;

void citire_graf(){
    int nod1, nod2;

    cin >> n >> m >> h;

    for(int i = 1; i <= n; i++){
        cin >> graf[i].cost;
    }
    for(int i = 1; i <= m; i++){
        cin >> nod1 >> nod2;
        graf[nod1].vecini.push_back(nod2);
    }
}

void preinitializare_timpi_tarjan(){
    for(int i = 1; i <= n; i++){
        graf[i].inStiva = graf[i].vizitat = 0;
        graf[i].numar_componenta = 0;
        graf[i].timp_descoperit = graf[i].timp_atins = INF;
    }
}

void dfs_tarjan(int nod){
    graf[nod].timp_descoperit = graf[nod].timp_atins = ++timp;
    graf[nod].inStiva = 1;
    st.push(nod);

    for(int vecin : graf[nod].vecini){
        if(graf[vecin].timp_descoperit == INF){
            dfs_tarjan(vecin);
        }

        if(graf[vecin].inStiva){
            graf[nod].timp_atins = min(graf[nod].timp_atins, graf[vecin].timp_atins);
        }
    }

    if(graf[nod].timp_atins == graf[nod].timp_descoperit){
        nr_componente++;

        while(st.top() != nod){
            graf[st.top()].numar_componenta = nr_componente;
            graf[st.top()].inStiva = 0;
            st.pop();
        }

        graf[nod].numar_componenta = nr_componente;
        graf[nod].inStiva = 0;
        st.pop();
    }
}

void tarjan(){
    preinitializare_timpi_tarjan();

    timp = nr_componente = 0;
    for(int i = 1; i <= n; i++){
        if(graf[i].timp_descoperit == INF){
            dfs_tarjan(i);
        }
    }
}

void dfs_creare_dag(int nod){
    graf[nod].vizitat = 1;
    dag[graf[nod].numar_componenta].cost += graf[nod].cost;
    dag[graf[nod].numar_componenta].cost_componenta = dag[graf[nod].numar_componenta].cost;

    for(int vecin : graf[nod].vecini){
        if(!graf[vecin].vizitat){
            dfs_creare_dag(vecin);
        }

        if(graf[nod].numar_componenta != graf[vecin].numar_componenta){
            dag[graf[nod].numar_componenta].vecini.push_back(graf[vecin].numar_componenta);
        }
    }
}

void creare_dag(){
    for(int i = 1; i <= n; i++){
        if(!graf[i].vizitat){
            dfs_creare_dag(i);
        }
    }
}

void dfs_sortare_topologica(int nod){
    dag[nod].vizitat = 1;

    for(int vecin : dag[nod].vecini){
        if(!dag[vecin].vizitat){
            dfs_sortare_topologica(vecin);
        }
    }

    topo_sort.push_back(nod);
}

void sortare_topologica(){
    for(int i = 1; i <= nr_componente; i++){
        if(!dag[i].vizitat){
            dfs_sortare_topologica(i);
        }
    }
}

void resetare_vizite(){
    for(int i = 1; i <= nr_componente; i++){
        dag[i].vizitat = 0;
    }
}

void calculare_costuri(){
    dag[graf[h].numar_componenta].vizitat = 1;

    for(int i = topo_sort.size() - 1; i >= 0; i--){
        if(dag[topo_sort[i]].vizitat){
            for(int vecin : dag[topo_sort[i]].vecini){
                dag[vecin].cost = max(dag[topo_sort[i]].cost + dag[vecin].cost_componenta, dag[vecin].cost);
                dag[vecin].vizitat = 1;
            }
        }
    }
}

void calculare_dag(){
    sortare_topologica();
    resetare_vizite();
    calculare_costuri();
}

void calulcare_si_afisare_solutii(){
    for(int i = 1; i <= n; i++){
        if(!dag[graf[i].numar_componenta].vizitat){
            cout << 0 << '\n';
        }
        else{
            cout << dag[graf[i].numar_componenta].cost << '\n';
        }
    }
}

int main(){
    citire_graf();

    tarjan();
    creare_dag();
    calculare_dag();

    calulcare_si_afisare_solutii();

    return 0;
}