Cod sursa(job #903127)

Utilizator TwistedFaithStanescu Jean Alexandru TwistedFaith Data 1 martie 2013 18:38:28
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
/* Sortare topologica */
#include <fstream>
#include <vector>

using namespace std;

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

unsigned int N; long int M; bool Mark[50002];
vector <unsigned int> Tab[50002], Sol;

void Citire()
{
    fin>>N>>M; unsigned int x,y;
    while(fin>>x>>y) Tab[x].push_back(y);
}

void Afisare()
{
    while(Sol.size()) {fout<<Sol.back()<<' '; Sol.pop_back();}
}

/* Parcurgere in adancime pentru a calcula timpii de terminare pentru fiecare
varf. Pe masura ce fiecare varf este terminat, acesta este scris sau salvat. */

void DFS(unsigned int Nod)
{
    vector<unsigned int>::iterator it;
    Mark[Nod]=1;

    for(it=Tab[Nod].begin(); it!=Tab[Nod].end(); it++)
        if(!Mark[*it])
            DFS(*it);

    Sol.push_back(Nod);
}

void S_Topologica()
{
    for(unsigned int i=1;i<=N;i++)
        if(!Mark[i])
            DFS(i);
}

int main()
{
    Citire();
    S_Topologica();
    Afisare();
}