Cod sursa(job #390092)

Utilizator mihaimoldovanMihai Moldovan mihaimoldovan Data 2 februarie 2010 21:46:10
Problema Sortare topologica Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include<fstream>
using namespace std;
struct nod
{
	int info;
	nod *next;
};
#define nn 50000
nod *g[nn],*t;
int n,grad[nn],v[nn];
void adauga(int a, int b)//adaugare nod la stanga
{
	t=new nod;
	t->info=b;
	t->next=g[a];
	g[a]=t;
	++grad[b];//cresc gradul exterior al lui b
}
int main()
{
	ifstream fin("sortaret.in");
	int i,x,a,b,m;//pt ca il folosesc doar la citire
	fin>>n>>m;
	for(;m;--m)
	{
		fin>>a>>b;
		adauga(a,b);
	}
	fin.close();
	for(i=1;i<=n;++i)
		if(grad[i]==0)//daca are grad exterior 0 atunci il adaug in coada
			v[++v[0]]=i;//in v[0] tin minte nr de elemente din coada
	for(i=1;i<=n;++i)
	{
		x=v[i];
		for(t=g[v[i]];t;t=t->next)//parcurg graful
		{
			--grad[t->info];//scad gradul exterior
			if(grad[t->info]==0)v[++v[0]]=t->info;//daca gradul exterior ajunge 0 atunci adaug elementul in coada
		}
	}
	FILE *f=fopen("sortaret.out","w");
	for(i=1;i<=n;++i)//v[0] ajunge sa fie n
		fprintf(f,"%d ",v[i]);//afisez coada
	fclose(f);
	return 0;
}