Cod sursa(job #1449544)

Utilizator deneoAdrian Craciun deneo Data 9 iunie 2015 22:35:58
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include <fstream>
#include <queue>
#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 (vector<int>::iterator it = graf[nod].begin(); it != graf[nod].end(); ++it) {
            --nrMuchii[*it];
            if (nrMuchii[*it] == 0)
                coada[++pozitie] = *it;
        }
    }

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