Cod sursa(job #1038940)

Utilizator pulseOvidiu Giorgi pulse Data 22 noiembrie 2013 11:43:16
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <fstream>
#include <vector>
#include <cstring>

using namespace std;

ifstream fin("sortaret.in"); ofstream fout("sortaret.out");

const int NMAX=50100;
int n, m, gext[NMAX], Q[NMAX];
vector <int> G[NMAX];

void read ()
{
    fin>>n>>m;
    memset (gext, 0, sizeof(gext));
    for (int i=1, nod1, nod2; i<=m; ++i)
    {
        fin>>nod1>>nod2;
        G[nod1].push_back(nod2);
        gext[nod2]++;
    }
}

void solve ()
{
    vector <int>::iterator it;
    int x;

    for (int i=1; i<=n; ++i)
    {
        if (gext[i]==0)
        {
            ++Q[0];
            Q[Q[0]]=i;
        }
    }

    for (int i=1; i<=n; ++i)
    {
        x=Q[i];
        for (it=G[x].begin(); it!=G[x].end(); ++it)
        {
            gext[*it]--;
            if (gext[*it]==0)
            {
                ++Q[0];
                Q[Q[0]]=*it;
            }
        }
    }
}

void print ()
{
    for (int i=1; i<=n; ++i)
        fout<<Q[i]<<" ";
    fout<<"\n";
}

int main ()
{
    read ();
    solve ();
    print ();
}