Cod sursa(job #1869985)

Utilizator Coroian_DavidCoroian David Coroian_David Data 6 februarie 2017 11:56:16
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include <cstdio>

using namespace std;

FILE *f, *g;

int n, m;

int lst[50001];
int urm[100001];
int nod[100001];

int k;

int np[50001];

int v[50001], sr;

void add(int a, int b)
{
    k ++;

    nod[k] = b;
    urm[k] = lst[a];

    lst[a] = k;

    np[b] ++;
}

void readFile()
{
    f = fopen("sortaret.in", "r");

    fscanf(f, "%d%d", &n, &m);

    int i;
    int a, b;
    for(i = 1; i <= m; i ++)
    {
        fscanf(f, "%d%d", &a, &b);

        add(a, b);
    }

    fclose(f);
}

int nivel[100001];

void solve()
{
    int total = 0;
    int crlvl = 0;

    int i, j;
    int p;
    while(total < n)
    {
        ++ crlvl;

        for(i = 1; i <= n; i ++)
        {
            if(np[i] == 0)
            {
                nivel[i] = crlvl;

                v[++ sr] = i;

                total ++;
            }
        }

        for(i = 1; i <= n; i ++)
        {
            if(nivel[i] == crlvl)
            {
                np[i] = -1;

                for(p = lst[i]; p != 0; p = urm[p])
                {
                    np[nod[p]] --;
                }
            }
        }
    }
}

void printFile()
{
    g = fopen("sortaret.out", "w");

    int i;
    for(i = 1; i <= sr; i ++)
        fprintf(g, "%d ", v[i]);

    fclose(g);
}

int main()
{
    readFile();

    solve();

    printFile();

    return 0;
}