Cod sursa(job #716871)

Utilizator halianStefanca Stefan halian Data 19 martie 2012 12:44:36
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
#define FI fopen("sortaret.in","r")
#define FO fopen("sortaret.out","w")

vector <long> nod[50001];
long n,m,inList[50001];
long inc[500001];
queue <long> sol,list;

void citeste(FILE *f) {
	long i,a,b;
	fscanf(f,"%li%li",&n,&m);
	for(i=0;i<m;i++) {
		fscanf(f,"%li%li",&a,&b);
		nod[a].push_back(b);
		inc[b]++;
	}
}

void sortareTopologica() {
	long front,lim,i;
	while(!list.empty()) {
		front=list.front();
		list.pop();
		sol.push(front);
		lim=nod[front].size();
		for(i=0;i<lim;i++) {
			inc[nod[front][i]]--;
			m--;
			if(inc[nod[front][i]]==0)
				list.push(nod[front][i]);
		}
	}
}

void scrie(FILE *f) {
	while(!sol.empty()) {
		fprintf(f,"%li ",sol.front());
		sol.pop();
	}
}

int main() {
	long i;
	citeste(FI);
	for(i=1;i<=n;i++)
		if(inc[i]==0)
			list.push(i);
	sortareTopologica();
	scrie(FO);
	return 0;
}