Cod sursa(job #1820397)

Utilizator iuliastoianIulia Stoian iuliastoian Data 1 decembrie 2016 17:36:26
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include <fstream>
#include <set>
using namespace std;

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

const int Dim = 50005;

struct nod {
    int info;
    nod * urm;
};

nod * prim;
nod * ultim;
set<int> G[Dim];
bool v[Dim];
int n, m;

void ReadGraph();
void Adaugare_Sfarsit(int x);
void Df(int x);
void Write();

int main()
{
    ReadGraph();
    Df(1);
    Write();

    fin.close();
    fout.close();
    return 0;
}

void ReadGraph()
{
    fin >> n >> m;
    int x, y;
    for (int i = 1; i <= m; ++i) {
        fin >> x >> y;
        G[x].insert(y);
    }
}

void Adaugare_Inceput(int x)
{
    if ( prim == nullptr ) {
        prim = new nod;
        prim->info = x;
        prim->urm = 0;
        ultim = prim;
    }
    else {
        nod * p = new nod;
        p->info = x;
        p->urm = prim;
        prim = p;
    }
}

void Df(int x)
{
	v[x] = true;

	for (auto it = G[x].begin(); it != G[x].end(); ++it)
		if ( !v[*it] )
			Df(*it);

    Adaugare_Inceput(x);
}

void Write()
{
    for ( auto it = prim; it != nullptr; it = it->urm )
        fout << it->info << ' ';
}