Cod sursa(job #776660)

Utilizator SteveStefan Eniceicu Steve Data 10 august 2012 10:30:33
Problema Sortare topologica Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <fstream>
#include <list>
#include <vector>

using namespace std;

int N, M, j = -1;
list <int> in[50005];
list <int> out[50005];
int v[50005];
vector <int> setlol;

void Citire () {
    ifstream fin ("sortaret.in");
    fin >> N >> M;
    int a, b;
    for (int i = 0; i < M; i++)
    {
        fin >> a >> b;
        out[a].push_back (b);
        in[b].push_back (a);
    }
    fin.close ();
    for (int i = 1; i <= N; i++)
        if (in[i].empty ()) setlol.push_back (i);
}

void Business () {
    int a, b, c;
    ofstream fout ("sortaret.out");
    while (!setlol.empty ())
    {
        a = setlol.back ();
        setlol.pop_back ();
        fout << a << " ";
        while (!out[a].empty ())
        {
            b = out[a].back ();
            in[b].remove (a);
            if (in[b].empty ()) setlol.push_back (b);
            out[a].pop_back ();
        }
    }
    fout.close ();
}

int main () {
    Citire ();
    Business ();
    return 0;
}