Cod sursa(job #372545)

Utilizator loginLogin Iustin Anca login Data 10 decembrie 2009 19:10:29
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
# include <fstream>
# include <cstdlib>
using namespace std;
int *a[50003], n, nro, d[50003], o[50003], m;

void dfs (int k)
{
	d[k]=1;
	for (int i=1;i<=a[k][0];i++)
		if (d[a[k][i]]==-1)
			dfs(a[k][i]);
	o[++nro]	 = k;
}

int main ()
{
	int i, j;
	ifstream fin ("sortaret.in");
	ofstream fout ("sortaret.out");
	fin>>n>>m;
	for (i=1;i<=n;i++)  
    {  
        a[i]=(int*) malloc(1*sizeof(int));
        a[i][0]=0, d[i]=-1;
	}
    
	for (;m;--m)
    {
        fin>>i>>j;
        a[i][0]++;
        a[i]=(int *) realloc(a[i], (a[i][0]+1)*sizeof(int));
        a[i][a[i][0]]=j;
    }
	for (i=1;i<=n;i++)
		if (d[i]==-1)
			dfs(i);
	for (i=n;i;i--)
		fout<<o[i]<<" ";
	return 0;
	
}