Cod sursa(job #633314)

Utilizator Marius_mFMI-M2 Marius Melemciuc Marius_m Data 13 noiembrie 2011 15:58:14
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include<stdio.h>
#include<vector>

using namespace std;

vector<int> a[50001],sol;
int viz[50001];

FILE *c,*d;

void DFS(int v)
{	long int st[50001],vf,primul,k,j;
	vf=1;
	st[vf]=v;
	viz[v]=1;
	while(vf>=1)	{
		primul=st[vf];
		k=0;
		for(j=0;j<a[primul].size()&&k==0;j++)
			if(viz[a[primul][j]]==0)	
				k=1;
		if(k==1)	{
				j--;
				vf++;
				st[vf]=a[primul][j];
				viz[a[primul][j]]=1;	
				}
		else
			{	sol.push_back(st[vf]);
				vf--;	}
				
	}
}

int main()
{	long int i,j,n,m,x,y;
	c=fopen("sortaret.in","r");
	d=fopen("sortaret.out","w");
	fscanf(c,"%ld %ld",&n,&m);
	for(i=1;i<=m;i++)	{
		fscanf(c,"%ld %ld",&x,&y);
		a[x].push_back(y);	}
	for(i=1;i<=n;i++)
		if(viz[i]==0)
			DFS(i);
	for(i=sol.size()-1;i>=0;i--)
		fprintf(d,"%ld ",sol[i]);
	fclose(c);
	fclose(d);
	return 0;
}