Cod sursa(job #1581339)

Utilizator PraetorGrigorosoaia Florin Praetor Data 26 ianuarie 2016 19:10:13
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include<fstream>
#define NRMAXNXQ 5001 // 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][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, "%ud%ld", &nr_nxq, &nr_arce);

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

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

        LA[x][0]++;
        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;
}