Cod sursa(job #597019)

Utilizator Brz_VladBrezae Vlad Brz_Vlad Data 20 iunie 2011 19:22:47
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
#include <stdio.h>

 struct nod{
	int x;
	nod* next;
};

 struct QUEUE{
	nod* start;
	nod* end;
};

QUEUE L;
QUEUE *NIn;
bool *vizitat;

void InitQ(QUEUE &q)
{
	q.start = NULL;
	q.end = NULL;
}

void AddQ(QUEUE &q,int x)
{
	if(q.start == NULL)
	{
		nod *nou = new nod;
		nou->next = NULL;
		nou->x = x;
		q.start = nou;
		q.end = nou;
	}
	else
	{
		nod *nou = new nod;
		nou->next = NULL;
		nou->x = x;

		q.end->next = nou;
		q.end = nou;
	}
}

int PopQ(QUEUE &q)
{
	if(q.start == NULL)
		return -1;
	int ret = q.start->x;
	nod *pt = q.start;
	q.start = q.start->next;
	delete pt;
	return ret;	
}

void viziteaza(int i)
{
	if(!vizitat[i]){
		vizitat[i]=true;
		int x;
		while((x=PopQ(NIn[i]))!=-1)
			viziteaza(x);		

		AddQ(L,i);
	}
}

int main(int argc, char* argv[])
{
	int n,m;
	int i;

	bool *iese;
	FILE *fpr,*fpw;
	fpr = fopen("sortaret.in","r");
	fpw = fopen("sortaret.out","w");

	fscanf(fpr,"%d %d",&n,&m);
	NIn = new QUEUE[n+1];
	vizitat = new bool[n+1];
	iese = new bool[n+1];

	for(i=1;i<=n;i++){
		InitQ(NIn[i]);
		vizitat[i]=false;
		iese[i]=false;
	}

	for(i=0;i<m;i++){
		int start,end;
		fscanf(fpr,"%d %d",&start,&end);
		AddQ(NIn[end],start);
		iese[start]=true;
	}

	for(i=1;i<=n;i++)
		if(! iese[i])
			viziteaza(i);

	for(i=0;i<n;i++)
		fprintf(fpw,"%d ",PopQ(L));

	return 0;
}