Cod sursa(job #484103)

Utilizator georgelRector George georgel Data 12 septembrie 2010 01:04:16
Problema Sortare topologica Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include<fstream>
#define Max 50000

using namespace std;

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

struct Nod
{
	int suc;
	Nod *urm;
};
int n,m;
int contor[Max],c[Max],gasit;
Nod *a[Max];
void adauga(int x,int y)
{
	Nod *p,*d;
	p=a[x];
	d = new Nod;
	d->urm = 0;
	d-> suc = y;
	if(p == 0)
		a[x] = d;
	else
	{
		while(p->urm) p = p->urm;
		p->urm = d;
	}
}
int main()
{
	int i,x,y,k=1;
	fin>>n>>m;
	for(i = 1; i <= m; i++)
	{
		fin>>x>>y;
		contor[y]++;
		adauga(x,y);
	}
	
	do
	{
		gasit = 1;
		for(i = 1; i <= n; i++)
			if(contor[i] == 0)
			{
				c[k++] = i;
				contor[i] = -1;
				Nod *p;
				for(p = a[i]; p != NULL; p=p->urm)
					contor[p->suc]--;
				gasit = 0;
			}
	}while(!gasit);
	for(i = 1; i < k; i++)
		fout<<c[i]<<" ";
	/*fout<<"\n";
	for(i = 1; i <= n; i++)
	{
		fout<<i<<": ";
		Nod *p;
		for(p = a[i]; p != NULL; p=p->urm)
			fout<<p->suc<<" ";
		fout<<"\n";
	}*/
	return 0;
}