Cod sursa(job #1427109)

Utilizator RaileanuCristian Raileanu Raileanu Data 1 mai 2015 15:45:39
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 kb
#include <fstream>
#include <list>
using namespace std;
ifstream f1("sortaret.in");
ofstream f2("sortaret.out");
#define MX 50010

int n,m, c[MX], k, nr_servant[MX], sol[MX];
list<int> master[MX];

int main()
{
    int i, x, y;

    f1>>n>>m;               // we have n people and m relations between them
    for (i=1; i<= m; i++)
    {
        f1>>x>>y;                     // x is the master of y
        master[y].push_back(x);     // be my servant y !
        nr_servant[x]++;            // i have more servants now ! Muahaha
    }

    for (i=1; i<=n; i++)            // we shall kill the servants first, so put them on the black list
        if ( nr_servant[i] == 0 )
            c[++k]= i;

    int p=n;

    while (k)
    {
        sol[p--]= c[1];                 // put the sevant on the killing list

        for (list<int>::iterator it= master[ c[1] ].begin(); it!= master[ c[1] ].end(); ++it )
        {                           // for every master he has
            nr_servant[ *it ]--; // let the master know that he's dead

            if ( nr_servant[ *it ] == 0 )    // it the master has no servants then he is a servant
                c[++k]= *it;                 // put him on the killing list
        }

        c[1]= c[k--];                               // the last will be the first
    }

    for (i=1; i<=n; i++)    // now this is the killing order in which masters die first
        f2<<sol[i]<<" ";

    f2.close();
    return 0;       // obey me world !
}