Cod sursa(job #433022)

Utilizator nandoLicker Nandor nando Data 3 aprilie 2010 10:24:30
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include <cstdio>
#include <vector>

using namespace std;

#define NMAX 50010

typedef vector<int>::iterator iter;

vector <int> G[NMAX],list;
char color[NMAX];
int n,m;


FILE* fin=fopen("sortaret.in","r");
FILE* fout=fopen("sortaret.out","w");

void DFS(int k){
	color[k]=1;
	for(iter it=G[k].begin();it!=G[k].end();it++){
		if(color[*it]==0){
			DFS(*it);
		}
	}
	color[k]=2;
	list.push_back(k);
}

int main(){
	fscanf(fin,"%d %d\n",&n,&m);
	
	int x,y;
	for(int i=0;i<m;i++){
		fscanf(fin,"%d %d\n",&x,&y);
		G[x].push_back(y);
	}
	
	for(int i=1;i<=n;i++){
		if(color[i]==0){
			DFS(i);
		}	
	}

	for(iter it=list.end()-1;it>=list.begin();it--){
		fprintf(fout,"%d ",*it);
	}

	fclose(fin);
	fclose(fout);
	return 0;
}