Cod sursa(job #2299343)

Utilizator CojocariuAlexandruCojocariu Alexandru CojocariuAlexandru Data 9 decembrie 2018 12:59:07
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb
#include <cstdio>
#include <vector>
#define NMAX 50005

using namespace std;

const char inname[] = "sortaret.in";
const char outname[] = "sortaret.out";
FILE *fin = fopen(inname, "r");
FILE *fout = fopen(outname, "w");

int n, m, vizitat[NMAX];

struct Lista{
    vector<int> vecini;
};
Lista L[NMAX];
vector<int> sortareFinala;

void citire();
void sortareTopologica();
void DFS(int);
void afisare();

int main(){
    citire();
    sortareTopologica();
    afisare();
    fclose(fin);
    fclose(fout);
    return 0;
}

void citire(){
    int i, x, y;
    fscanf(fin, "%d", &n);
    fscanf(fin, "%d", &m);
    for(i=1; i<=m; i++){
        fscanf(fin, "%d", &x);
        fscanf(fin, "%d", &y);
        L[x].vecini.push_back(y);
        }
}

void sortareTopologica(){
    int i;
    for(i=1; i<=n; i++)
        if(vizitat[i] == 0)
            DFS(i);
}

void DFS(int k){
    int i;
    vizitat[k] = 1;
    for(i=0; i<L[k].vecini.size(); i++)
        if(vizitat[L[k].vecini[i]] == 0)
            DFS(L[k].vecini[i]);
    sortareFinala.push_back(k);
}

void afisare(){
    int i;
    for(i=sortareFinala.size()-1; i>=0; i--)
        fprintf(fout, "%d ", sortareFinala[i]);
    fprintf(fout, "\n");
}