Cod sursa(job #903104)

Utilizator TwistedFaithStanescu Jean Alexandru TwistedFaith Data 1 martie 2013 18:32:32
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 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];

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

/* 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);

    fout<<Nod<<' ';
}

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

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