Cod sursa(job #886975)

Utilizator evodaniVasile Daniel evodani Data 23 februarie 2013 14:20:22
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <cstdio>
#include <vector>
#define NMAX 50001
using namespace std;
FILE *fin, *fout;
vector <int> graf[NMAX];
int gradi[NMAX], vect[NMAX], n, m, coada[NMAX];
void sort ();
int main()
{
    int i, a, b;
    fin=fopen("sortaret.in", "r"); fout=fopen("sortaret.out", "w");
    fscanf (fin, "%d%d", &n, &m);
    for (i=1; i<=m; ++i) { fscanf (fin, "%d%d", &a, &b); graf[a].push_back(b); ++gradi[b]; }
    sort();
    fclose(fin); fclose(fout);
    return 0;
}
void sort () {
    int ic=1, sc=0, ct=0, i, vf;
    for (i=1; i<=n; ++i) if (!gradi[i]) coada[++sc]=i;
    while (ic<=sc) {
        vf=coada[ic++];
        vect[++ct]=vf;
        for (i=0; i<graf[vf].size(); ++i) { --gradi[graf[vf][i]]; if (!gradi[graf[vf][i]]) coada[++sc]=graf[vf][i]; }
    }
    for (i=1; i<=n; ++i) fprintf (fout, "%d ", vect[i]);
}