Cod sursa(job #765744)

Utilizator R.A.RFMI Romila Remus Arthur R.A.R Data 9 iulie 2012 10:05:29
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <fstream>

using namespace std;

const int NMAX=50007;

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

struct nod
{
    int data;
    nod *next;
}*V[NMAX];

bool Uz[NMAX];
int ST[NMAX],Vf;
int N,M;

void Add(int x,int y)
{
    nod *aux = new nod;
    aux->next = V[x];
    aux->data = y;
    V[x] = aux;
}

void Push(int x)
{
    ST[++Vf] = x;
}

void DFS(int x)
{
    Uz[x] = 1;
    int y;
    nod *cont = new nod;
    for(cont = V[x];cont!=NULL;cont=cont->next)
    {
        y = cont->data;
        if(!Uz[y])
            DFS(y);
    }
    Push(x);
}

int main()
{
    int x,y;
    in>>N>>M;
    while(M--)
    {
        in>>x>>y;
        Add(x,y);
        //Add(y,x);
    }
    for(x=1;x<=N;x++)
        if(!Uz[x])
            DFS(x);
    while(Vf)
        out<<ST[Vf--]<<' ';
    out.close();
    return 0;
}