Cod sursa(job #2405285)

Utilizator minculescualex9Minculescu Alex minculescualex9 Data 14 aprilie 2019 11:51:22
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 kb
#include <iostream>
#include <fstream>

using namespace std;

#define nMax 50001
#define mMax 100001

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

typedef struct nod{
    int vf;
    nod *next;
} *Lista, NOD;

Lista L[nMax]; // Listele de vecini ptr fiecare nod
Lista Sortat;
int N, M, Muchii[mMax];
bool Visited[nMax];

void Add(int x, int y){
    Lista p = new NOD;
    p -> vf = y;
    p -> next = L[x];
    L[x] = p;
}

void push(int nod){
    Lista p = new NOD;
    p -> vf = nod;
    p -> next = Sortat;
    Sortat = p;
}

void DFS(int nod){
    Visited[nod] = true;

    for(Lista p = L[nod]; p > 0; p = p -> next)
        if( Visited[p -> vf] == false )
           DFS(p -> vf);
    push(nod);
}


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


int main()
{
    //Citire
    fin >> N >> M;
    for( ; M > 0; --M ){
        int x, y;
        fin >> x >> y;

        Add(x, y);
    }

    S_Topologica();

    //Scriere
    for(Lista p = Sortat; p; p = p -> next)
        fout << p -> vf << " ";


    fin.close();
    fout.close();
    return 0;
}