Cod sursa(job #1413796)

Utilizator Ionut228Ionut Calofir Ionut228 Data 2 aprilie 2015 09:02:09
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <fstream>
#include <vector>

using namespace std;

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

int N, M;
int Q[50005], grd[50005];
vector<int> V[50005];

int main()
{
    fin >> N >> M;
    for (int i = 1, nod1, nod2; i <= M; ++i)
    {
        fin >> nod1 >> nod2;
        V[nod1].push_back(nod2);
        ++grd[nod2];
    }

    for (int i = 1; i <= N; ++i)
        if (!grd[i])
            Q[++Q[0]] = i;

    for (int i = 1; i <= Q[0]; ++i)
    {
        int nod = Q[i];
        for (vector<int>::iterator it = V[nod].begin(); it != V[nod].end(); ++it)
        {
            --grd[*it];
            if (!grd[*it])
                Q[++Q[0]] = *it;
        }
    }

    for (int i = 1; i <= Q[0]; ++i)
        fout << Q[i] << ' ';
    fout << '\n';

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