Cod sursa(job #751361)

Utilizator Theorytheo .c Theory Data 25 mai 2012 20:53:03
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include<fstream>
#include<stdlib.h>
#define nmax 50004
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
int n, m, *A[nmax], Q[nmax], Nr, gr[nmax];
void solve(void)
{
    for(int i = 1; i <= n; ++i)
        if(gr[i] == 0)
            Q[++Nr] = i;
    for(int i = 1; i <= n; ++i)
    {
        //int x = Q[i];
        for(int j = 1; j <= A[Q[i]][0]; j++)
        {
            gr[ A[Q[i]][j] ]--;
            if(gr[A[Q[i]][j]] == 0 )
                Q[++Nr] = A[Q[i]][j];

        }
    }
    for(int i = 1; i <= n; ++i)
        fout << Q[i] <<" ";
}
void read()
{
    fin >> n >>m;
    for(int i = 0; i <= n ;++i)
    {
        A[i] = (int * ) realloc(A[i],  sizeof(int));
        A[i][0] = 0;
    }
    for(int k = 1; k <= m; k++)
    {
        int i, j;
        fin >> i >> j;
        A[i][0]++;
        A[i]= (int *) realloc(A[i], sizeof(int ) * (A[i][0] + 1));
        A[i][A[i][0]] = j;
        gr[j]++;
    }
    solve();

}
int main()
{
    read();
    fin.close();
    return 0;

}