Cod sursa(job #993272)

Utilizator Ionut228Ionut Calofir Ionut228 Data 3 septembrie 2013 16:15:56
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include <fstream>
#include <vector>

using namespace std;

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

int N, M;
int V[50001][50001], grad_interior[50001];
bool W[50001];

int main()
{
    fin >> N >> M;
    for (int i = 1, nod1, nod2; i <= M; ++i)
    {
        fin >> nod1 >> nod2;
        V[nod1][nod2] = 1;
        ++grad_interior[nod2];
    }
    bool ok = false;
    while (!ok)
    {
        bool k = true;
        ok = true;
        for (int i = 1; i <= N; ++i)
        {
            if (grad_interior[i] == 0 && k)
            {
                for (int j = 1; j <= N; ++j)
                    if (V[i][j])
                    {
                        if (grad_interior[j] >= 1)
                            --grad_interior[j];
                    }
                fout << i << " ";
                grad_interior[i] = -1;
                W[i] = true;
                k = false;
            }
            if (W[i] == false)
                ok = false;
        }
    }

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