Cod sursa(job #1042267)

Utilizator L.DanielLungu Daniel L.Daniel Data 26 noiembrie 2013 20:20:12
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include<fstream>
using namespace std;
fstream f("sortaret.in", ios::in);
fstream g("sortaret.out", ios::out);
int viz[50005], n, m;
struct lista { int val;
lista*urm;
};
lista*v[50005];
lista*cap=NULL;
void Adaug(lista*&, int);
void add(lista*&d, int x)
{
	lista*p = new lista;
	p->val = x;
	p->urm = d;
	d = p;
}
void DFS(int x)
{
	lista*p = new lista;
	viz[x] = 1;
	for (p = v[x]; p != NULL;p=p->urm)
	if (viz[p->val] == 0)DFS(p->val);
	Adaug(cap, x);
}
void Parcurgere_Topologica()
{
	int i;
	for (i = 1; i <= n;i++)
	if (viz[i] == 0)DFS(i);
}
void Adaug(lista*&cap,int x)
{
	lista*p = new lista;
	p->val = x;
	p->urm = cap;
	cap = p;
}
void Afisare(lista*cap)
{
	lista*p = new lista;
	for (p = cap; p != NULL; p = p->urm)
		g << p->val << " ";
}
int main()
{
	int x, y, i;
	f >> n >> m;
	for (i = 1; i <= m; i++)
	{
		f >> x >> y;
		add(v[x], y);

	}
	Parcurgere_Topologica();
	Afisare(cap);

	return 0;
}