Cod sursa(job #2371868)

Utilizator AndreiSopSopterean Andrei Mihai AndreiSop Data 6 martie 2019 19:58:39
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.89 kb
#include <fstream>
using namespace std;

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

struct NOD
{
	int 	vf;
	NOD	*next;
};

int	N, M;
NOD	*L[50001];
int	viz[50001];
NOD	*coada;

void	add(int x, int y)
{
	NOD *nod = new NOD;
	nod->vf = y;
	nod->next = L[x];
	L[x] = nod;
}

void	read()
{
	int x, y, i;

	fin >> N >> M;
	for (i = 0; i < M; i++)
	{
		fin >> x >> y;
		add(x, y);
	
	}
	fin.close();
}

void	Push(int v)
{
	NOD *nod = new NOD;
	nod->vf = v;
	nod->next = coada;
	coada = nod;
}

void	DFS(int v)
{
	NOD *nod;

	viz[v] = 1;
	for (nod = L[v]; nod; nod=nod->next)
	{
		if (!viz[nod->vf])
			DFS(nod->vf);
	}
	Push(v);
}

void	sortare()
{
	int i;

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

void	afisare()
{
	NOD *nod;

	for (nod = coada; nod; nod = nod->next)
		fout<<nod->vf<<" ";
	fout<<endl;
	fout.close();
}

int 	main(void)
{
	read();
	sortare();
	afisare();
	return (0);
}