Cod sursa(job #993440)

Utilizator Ionut228Ionut Calofir Ionut228 Data 3 septembrie 2013 20:44:55
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <fstream>
#include <vector>

using namespace std;

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

int N, M;
vector<int> V[50001];
int degree[50001], Q[50001];

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

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

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

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

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