Cod sursa(job #426616)

Utilizator undogSavu Victor Gabriel undog Data 27 martie 2010 11:10:26
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include <fstream>
#include <cstdlib>

using namespace std;

int gradO[50005];
int* v[50005];
int vn[50005];
bool visited[50005];

int list[50005];
int listn;

void visit(int x){
	if(!visited[x]){
		visited[x]=true;
		int i;
		for(i=0;i<gradO[x];i++)
			visit(v[x][i]);
		list[listn++]=x;
	}
}

int main(){
	ifstream in("sortaret.in");
	ofstream out("sortaret.out");
	
	int n,m;
	
	in>>n>>m;
	
	int a,b,i;
	
	for(i=0;i<m;i++){
		in>>a>>b;
		gradO[a]++;
	}
	
	for(i=1;i<=n;i++)
		v[i]= (int*) malloc(gradO[i] * sizeof(int));
	
	in.seekg(0,ios::beg);
	
	in>>n>>m;
	
	for(i=0;i<m;i++){
		in>>a>>b;
		v[a][vn[a]++]=b;
	}
	
	for(i=1;i<=n;i++)
		visit(i);
		
	for(i=n-1;i>=0;i--)
		out<<list[i]<<' ';
		
	
	out<<'\n';
	
	return 0;
}