Cod sursa(job #426653)

Utilizator undogSavu Victor Gabriel undog Data 27 martie 2010 11:32:29
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <fstream>
#include <cstdlib>

using namespace std;

int main(){
	ifstream in("sortaret.in");
	ofstream out("sortaret.out");
	
	int n,m;
	int a,b,i;
	
	int gradO[50005];
	int* v[50005];
	int vn[50005];
	int visited[50005];
	
	
	in>>n>>m;
	
	for(i=1;i<=n;i++){
		visited[i]=0;
		vn[i]=0;
		gradO[i]=0;
	}
	
	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;
	}
	
	int st[100000];
	int st2[100000];
	
	int list[50005];
	int listn=0;
	
	int l=n-1;
	
	for(i=0;i<n;i++)
		st[i]=i+1;
	
	for(i=0;i<=2*n;i++)
		st2[i]=0;
	
		
	while(l>=0){
		if(visited[st[l]]>0){
			if(visited[st[l]]<2){
				list[listn++]=st[l];
				visited[st[l]]=2;
			}
			st2[l]=0;
			l--;
		}
		else{
			visited[st[l]]=1;
			while(visited[v[st[l]][st2[l]]]&&st2[l]<gradO[st[l]])
				st2[l]++;
			
			if(st2[l]<gradO[st[l]]){
				st[l+1]=v[st[l]][st2[l]];
				l++;
			}
		}
	}
	
	
	for(i=n-1;i>=0;i--)
		out<<list[i]<<' ';
		
	
	out<<'\n';
	
	return 0;
}