Cod sursa(job #303154)

Utilizator IeewIordache Bogdan Ieew Data 9 aprilie 2009 16:37:56
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <fstream>
using namespace std;
#include <stdlib.h>
#define NMAX 50001
int *v[NMAX],n,m,viz[NMAX],r[NMAX],q=0;

void rec(int x)
{int i;
viz[x]=1;
for(i=1;i<=v[x][0];i++)
	if(!viz[v[x][i]])rec(v[x][i]);
r[n-q++]=x;
}

int main()
{int i,a,b,c,j;
ifstream in("sortaret.in");
in>>n>>m;
for(i=1;i<=m;i++)
{
 in>>a>>b;
 viz[a]++;
}
in.close();
for(i=1;i<=n;i++)
	{
	 v[i]=(int*)malloc((viz[i]+1)*sizeof(int));
	 v[i][0]=0;
	 viz[i]=0;
	}
ifstream in2("sortaret.in");
in2>>n>>m;
for(i=1;i<=m;i++)
	{
	 in2>>a>>b;
	 v[a][++v[a][0]]=b;
	}
in2.close();
//for(i=1;i<=n;i++){cout<<i<<"       ";
//for(j=1;j<=v[i][0];j++)cout<<v[i][j]<<' ';cout<<'\n';}

for(i=1;i<=n;i++)
	if(!viz[i])rec(i);

ofstream out("sortaret.out");
for(i=1;i<=n;i++)out<<r[i]<<' ';out<<'\n';
out.close();
return 0;
}