Cod sursa(job #679089)

Utilizator Andreid91Ciocan Andrei Andreid91 Data 12 februarie 2012 19:11:40
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <fstream>
#include <vector>

using namespace std;

int n,m,timp,timpi[60000],timpe[50009],sol[100005],sw[50005],nr[50005];
vector <int> v[50005];

void df (int i)
{
	vector <int> :: iterator it;
	sw[i]=1;
	timpi[i]=++timp;
	for (it=v[i].begin();it<v[i].end();++it)
		if (sw[*it]==0)
			df (*it);
	timpe[i]=++timp;
}

void numar ()
{
	int i;
	for (i=1;i<=n;i++)
		if (nr[i]==0 && sw[i]==0)
			df (i);
		
	for (i=1;i<=n;i++)
		sol [timpe[i]]=i;
}

void gradin ()
{
	int i;
	vector <int > :: iterator it;
	for (i=1;i<=n;i++)
		for (it=v[i].begin();it<v[i].end();++it)
			nr[*it]++;
}

void citire ()
{
	int i,x,y;
	FILE *f;
	f=fopen ("sortaret.in","r");
	fscanf (f,"%d%d",&n,&m);
	for (i=1;i<=m;i++)
	{
		fscanf (f,"%d%d",&x,&y);
		v[x].push_back(y);
	}
	fclose (f);
}

void afisare ()
{
	int i;
	FILE *f ; f=fopen ("sortaret.out","w");
	for (i=2*n;i>0;--i)
		if (sol[i])
			fprintf (f,"%d ",sol[i]);
	
	fclose(f);
}

int main ()
{
	citire ();
	gradin();
	numar();
	afisare ();
	return 0;
}