Cod sursa(job #1393147)

Utilizator casuneanu.andreiCasuneanu Andrei Dan casuneanu.andrei Data 19 martie 2015 09:33:06
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include <fstream>
#include <vector>
using namespace std;
#define IN "sortaret.in"
#define OUT "sortaret.out"
#define DMAX 50008
#define pb push_back
#define INFO 0
ifstream fin(IN);
ofstream fout(OUT);

int n, m;

int c[DMAX];
int st, sf;

vector <int> g[DMAX];
int di[DMAX];//gradul interior

void citire();
inline void adauga(int x){c[++sf]=x;}
inline void reset(){sf=-1; st=0;}
inline int get_elem(){return c[st++];}
void sortare();


int main(){
    citire();
    sortare();

    int i;
    for (i=0; i<=sf; ++i)
        fout <<c[i]<<' ';
    fout <<'\n';
    fout.close();
    return 0;
}

void sortare(){
    int i, x, nr;
    while (sf-st>=0){
        x=get_elem();
        if (INFO)
            fout <<'\n'<<x;
        nr=g[x].size();

        for (i=0; i<nr; ++i){
            if (INFO)
                fout <<g[x][i]<<' ';
            --di[g[x][i]];
            if (!di[g[x][i]])
                adauga(g[x][i]);
        }
    }
}

void citire(){
    fin >>n>>m;

    int i;
    int x, y;
    for (i=1; i<=m; ++i){
        fin >>x>>y;
        g[x].pb(y);
        ++di[y];
    }

    reset();
    for (i=1; i<=m; ++i)
        if (!di[i])
            adauga(i);
}