Cod sursa(job #1449545)

Utilizator bogdanciurezubogdan ciurezu bogdanciurezu Data 9 iunie 2015 22:36:11
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <fstream>
#include <iostream>
#include <vector>
#define nmax 100500

using namespace std;
ifstream f("sortaret.in");
ofstream g("sortaret.out");

vector <int> graf[nmax];
int N, M, nrMuchii[nmax], coada[nmax], pozitie;

int main()
{int i, j, k, a, b;
    f>>N>>M;

    for(i = 1; i <= M; ++i){
        f>>a>>b;
        graf[a].push_back(b);
        ++nrMuchii[b];
    }

    for(i = 1; i <= N; ++i){
        if( !nrMuchii[i] ){
            coada[++pozitie] = i;
        }
    }

    int curPoz = 1; //procesam primul nod

    while(curPoz <= pozitie){
        int nod = coada[curPoz++];

        for (auto it : graf[nod]) {
            if (--nrMuchii[it] == 0)
                coada[++pozitie] = it;
        }
    }

    for(i = 1; i <= N; ++i)
        g<<coada[i]<<' ';
    g<<'\n';
    return 0;
}