Cod sursa(job #656978)

Utilizator noobakafloFlorin eu noobakaflo Data 5 ianuarie 2012 16:36:50
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include<fstream>
using namespace std;
#define N_MAX 50001

struct lista
{
	int nod;
	lista *next;
} *G[N_MAX];

long n,m,k,st[N_MAX]; 
bool vizitat[N_MAX];

void adauga(int i,int j)
{
	lista *q;
	q=new lista;    q->nod=j;
	q->next=G[i];   G[i]=q;
}

void Citire(void)
{
	int i,j;
	fstream f("sortaret.in",ios::in);
	f>>n>>m;
	while(f>>i>>j)
		adauga(i,j);
	f.close();
}

void DFS(int nod)
{
	lista *p;
	vizitat[nod]=1; //marchez nodul ca fiind vizitat
	for(p=G[nod]; p!=NULL; p=p->next)
		if(!vizitat[p->nod])
			DFS(p->nod);
	st[k++]=nod;
}


void Sortare_Topologica(void)
{
	int i;
	for(i=1; i<=n; i++)
		if(!vizitat[i])
			DFS(i);
}

void Afisare(void)
{
	fstream g("sortaret.out",ios::out);
	int i;
	for(i=n-1; i>=0; i--)
		g<<st[i]<<" ";
	g.close();
}


int main()
{
	Citire();
	Sortare_Topologica();
	Afisare();
	return 0;
}