Cod sursa(job #1131496)

Utilizator vlad.rusu11Rusu Vlad vlad.rusu11 Data 28 februarie 2014 20:33:51
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <fstream>
#include <vector>
#define NMax 50001
using namespace std;

int N, M, deg[NMax], Q[NMax];
vector<int> Nod[NMax];

int main()
{
    ifstream fin("sortaret.in");
    ofstream fout("sortaret.out");

    int a, b, i, x;
    vector<int>::iterator it;

    fin >> N >> M;
    for(i = 1 ; i <= M ; ++i)
    {
        fin >> a >> b;
        Nod[a].push_back(b);
        ++deg[b];
    }

    for(x = 1 ; x <= N ; ++x)
        if(deg[x] == 0)
            Q[++Q[0]] = x;

    for(i = 1 ; i <= N ; ++i)
    {
        x = Q[i];
        for(it = Nod[x].begin() ; it != Nod[x].end() ; ++it)
        {
            --deg[*it];
            if(deg[*it] == 0)
                Q[++Q[0]] = *it;
        }
    }

    for(i = 1 ; i <= N ; ++i)
        fout << Q[i] << ' ';

    fin.close();
    fout.close();
    return 0;
}