Cod sursa(job #2016495)

Utilizator catalinlupCatalin Lupau catalinlup Data 29 august 2017 15:42:29
Problema Sortare topologica Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <stdlib.h>
#define INFILE "sortaret.in"
#define OUTFILE "sortaret.out"
#define NMAX 50001
#define MMAX 110000
using namespace std;
ifstream in(INFILE);
ofstream out(OUTFILE);

int n,m;
int*A[NMAX];
bool viz[NMAX];
stack<int> st;


void Read(){
    in>>n>>m;
    for(int i=1;i<=n;i++){
        A[i]=(int*)realloc(A[i],sizeof(int));
    }
    for(int i=1;i<=m;i++){
        int x,y;
        in>>x>>y;


            A[x][0]++;
            A[x]=(int*)realloc(A[x],(A[x][0]+1)*sizeof(int));
            A[x][A[x][0]]=y;

    }
}

void DFS(int x){
    viz[x]=true;
    for(int i=1;i<=A[x][0];i++){
        if(!viz[A[x][i]])
            DFS(A[x][i]);
    }
    st.push(x);
}
void Afisare(){
    while(!st.empty()){
        out<<st.top()<<" ";
        st.pop();
    }
}

int main()
{
    Read();
    for(int i=1;i<=n;i++){
        if(!viz[i])
            DFS(i);
    }
    Afisare();
    return 0;
}