Cod sursa(job #1581422)

Utilizator PraetorGrigorosoaia Florin Praetor Data 26 ianuarie 2016 20:00:36
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 kb
#include<fstream>
#include<stdlib.h>
#define NRMAXNXQ 50001 // numarul maxim de noduri

using namespace std;

FILE*in;
ofstream out("sortaret.out");

unsigned int nr_nxq; // numarul de noduri
long nr_arce;
unsigned int *LA[NRMAXNXQ]; // lista de adiacenta
bool visited[NRMAXNXQ];
unsigned int sorted[NRMAXNXQ];
unsigned int k; // contor pentru sorted

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

    fscanf(in, "%d%ld", &nr_nxq, &nr_arce);
    // aloc memorie pentru gradul fiecarui varf
    for (unsigned i=1; i<=nr_nxq; i++)
    {
        LA[i]=(unsigned int *)realloc(LA[i], sizeof(unsigned int));
        LA[i][0]=0;
    }

    for (long i=1; i<=nr_arce; i++)
    {
        unsigned int x, y;

        fscanf(in, "%d%d", &x, &y);

        LA[x][0]++;
        // realocam memorie pentru lista de adiacenta a lui x
        LA[x]=(unsigned int *)realloc(LA[x], (LA[x][0]+1)*sizeof(unsigned int));

        LA[x][LA[x][0]]=y;
    }
}

void DFS(int nxq)
{
    visited[nxq]=true;

    for (unsigned int i=1; i<=LA[nxq][0]; i++)
        if (!visited[LA[nxq][i]])
            DFS(LA[nxq][i]);

    k++;
    sorted[k]=nxq;
}

void solve()
{
    for (unsigned int i=1; i<=nr_nxq; i++)
        if (!visited[i])
            DFS(i);
}

void show()
{
    for (unsigned int i=nr_nxq; i>=1; i--)
        out<<sorted[i]<<" ";
}

int main()
{
    read();
    solve();
    show();

    return 0;
}