Cod sursa(job #370554)

Utilizator titusuTitus C titusu Data 1 decembrie 2009 15:54:34
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
/*
	  	Se da un graf orientat. Sa se sorteze topologic graful.
				Se numeste sortare topologica o aranjare a nodurilor, cu prop. ca daca exista arcul (i,j) atunci i este in aranjare inaintea lui j.
				 */
#include <fstream>
#include <iostream>
using namespace std;
#define MAX 50001
int n, lista[MAX],nrLista, v[MAX];
struct nod{
		int info; nod * next;
};
nod * a[MAX];

void read();
void write();
void sort();
void dfs(int varf);

int main(){
		read();sort();write();
		return 0;
}

void read(){
		ifstream fin("sortaret.in");
		int m;
		fin>>n>>m;
		for(int i= 1; i<=n ; ++i)
			a[i] = NULL;
		for( ; m  ; m--){
			int i,j;
			fin>>i>>j;
			nod * p = new nod;
			p -> info = j;
			p -> next = a[i];
			a[i] = p;
		}
}

void write(){
		ofstream fout("sortaret.out");
		for(int i=n;i;--i)
			fout<<lista[i]<<" ";
}

void sort(){
	for(int i=1;i<=n;i++)
		if(!v[i])
			dfs(i);
}

void dfs(int varf){
	//cout<<varf<<" ";
	v[varf] = 1;
	for(nod *p = a[varf]; p ; p = p->next){
		if(!v[p->info])
			dfs(p->info);
	}
	lista[++nrLista] = varf;
}