Cod sursa(job #1572483)

Utilizator mihai.constantinConstantin Mihai mihai.constantin Data 18 ianuarie 2016 22:26:43
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <iostream>
#include <fstream>
using namespace std;

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

const int dmax = 50000;
const int dim = 100000;

int lst[dmax + 1];
int vf[dim + 1];
int urm[dim + 1];
int nr;

bool viz[dmax + 1];

int sol[dmax + 1];
int k;

int N, M;

void dfs(int x)
{
    int y, p;

    viz[x] = true;

    //PARCURG VECINII y AI LUI x

    p = lst[x];

    while(p)
    {
        y = vf[p];

        if(!viz[y]) dfs(y);

        p = urm[p];
    }

    sol[++k] = x;
}

void adauga(int x, int y)
{
    //ADAUGA IN LISTA LUI x PE y

    nr++;
    vf[nr] = y;
    urm[nr] = lst[x];
    lst[x] = nr;
}

int main()
{
    int i, x, y;

    in >> N >> M;

    for(i = 1; i <= M; i++)
    {
        in >> x >> y;

        adauga(x, y);

    }

    for(i = 1; i <= N; i++)
        if(!viz[i]) dfs(i);

    for(i = k; i >= 1; i--) out << sol[i] << " ";

    return 0;
}