Cod sursa(job #2664309)

Utilizator Stefan_DomuncoStefan Domunco Stefan_Domunco Data 28 octombrie 2020 14:06:06
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.11 kb
///Algoritmul lui Kahn
#include <bits/stdc++.h>

using namespace std;
vector < vector <int> >w;
queue <int> coada, solutie;
int grad_intern[50005];
int main()
{
    ifstream f("sortaret.in");
    ofstream g("sortaret.out");
    int n, m, i, nod1, nod2;
    f>>n>>m;
    w = vector< vector <int> >(n+1);
    for(i = 1; i <= m; ++i)
    {
        f>>nod1>>nod2;
        w[nod1].push_back(nod2);
        ++grad_intern[nod2];
    }

    for(i = 1; i <= n; ++i)
    {
        if(grad_intern[i] == 0)
            coada.push(i);
    }

    while(!coada.empty())
    {
        int nod_curent = coada.front();
        solutie.push(nod_curent);
        coada.pop();

        ///sterg muchiile
        for(i = 0; i < w[nod_curent].size(); ++i)
        {
            --grad_intern[w[nod_curent][i]];
            if(grad_intern[w[nod_curent][i]] == 0)
                coada.push(w[nod_curent][i]);
        }

        while(!w[nod_curent].empty())w[nod_curent].pop_back();

    }

    while(!solutie.empty())
    {
        g<<solutie.front()<<' ';
        solutie.pop();
    }

    return 0;
}