Cod sursa(job #575296)

Utilizator maritimCristian Lambru maritim Data 8 aprilie 2011 09:32:06
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include<stdio.h>
#include<malloc.h>

typedef struct _nod
{
	int info;
	struct _nod *adr;
} nod;

typedef struct
{
	struct _nod *cap;
} list;

int pred[50001];
list succ[50001];
int sol[50001];
int pf = 0;
int N;
int M;

void add(int a,int b)
{
	nod *q = succ[a].cap;
	int gata = 1;
	while(q && gata)
		if(q->info == b)
			gata = 0;
		else
			q = q->adr;
	if(!q)
	{
		pred[b] ++;
		nod *nou = (nod*)malloc(sizeof(nod));
		nou->info = b;
		nou->adr = succ[a].cap;
		succ[a].cap = nou;
	}
}

void citire(void)
{
	int a;
	int b;
	FILE *f = fopen("sortaret.in","r");
	
	fscanf(f,"%d %d",&N,&M);
	for(int i=1;i<=M;i++)
	{
		fscanf(f,"%d %d",&a,&b);
		add(a,b);
	}
	
	fclose(f);
}

void solve(int a)
{
	if(!pred[a])
	{
		sol[++pf] = a;
		pred[a] = -1;
		nod *q = succ[a].cap;
		while(q)
		{
			pred[q->info] --;
			solve(q->info);
			q = q->adr;
		}
	}
}

int main()
{
	FILE *f = fopen("sortaret.out","w");
	
	citire();
	for(int i=1;i<=N;i++)
		if(!pred[i])
			solve(i);
	if(pf == N)
	for(int i=1;i<=pf;i++)
		fprintf(f,"%d ",sol[i]);
	else
		fprintf(f,"-1");
	
	fclose(f);
	return 0;
}