Cod sursa(job #365531)

Utilizator titusuTitus C titusu Data 18 noiembrie 2009 23:24:32
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 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>
using namespace std;
#define MAX 50001
int grad[MAX], n, coada[MAX], v[MAX];
struct nod{
	int info; nod * next;
};
nod * a[MAX];

void read();
void write();
void sort();

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;
		grad[j]++;
		nod * p = new nod;
		p -> info = j;
		p -> next = a[i];
		a[i] = p;
	}
}

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

void sort(){
	int dr=0,st=1;
	for(int i =1 ; i <= n ;i++)
		if(grad[i] == 0)
			coada[++dr] = i;
	while(st<=dr){
		int k = coada[st];
		for(nod * p = a[k]; p ; p = p->next){
			int j = p->info;
			grad[j] --;
			if(grad[j] == 0)
				coada[++dr] = j;
		}
		st++;
	}
}