Cod sursa(job #814827)

Utilizator roots4Irimia Alexandru Gabriel roots4 Data 16 noiembrie 2012 10:00:03
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.64 kb
#include<stdio.h>
#include<vector>
#define DIM 50010

using namespace std;

FILE*f=fopen("sortaret.in","r");
FILE*g=fopen("sortaret.out","w");


vector<int>L[DIM];

int i,n,m,Sol[DIM],Fr[DIM],k,Grad[DIM];

void read(){
	int a,b;
	fscanf(f,"%d%d",&n,&m);
	
	for(int i=1;i<=m;i++){
		fscanf(f,"%d%d",&a,&b);
		L[a].push_back(b);
		Grad[b]++;
	}
}

void dfs(int x){
	for(int j=0;j<L[x].size();j++)
		dfs(L[x][j]);
	if(!Fr[x]){
		Sol[++k]=x;
		Fr[x]=1;
	}
	
}


int main(){
	
	read();
	
	for(i=1;i<=n;i++){
		if(!Grad[i]){
			dfs(i);
		}
	}
	
	for(i=k;i>=1;i--)
		fprintf(g,"%d ",Sol[i]);
	
	return 0;
}