Cod sursa(job #916733)

Utilizator dudutCancel Radu Constantin dudut Data 16 martie 2013 20:31:03
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<queue>
using namespace std;
struct nod {
	int info;
	nod *urm;
};

void adaug(nod *&start, int y) {
	nod *p;
	p = new nod;
	if ( p ){
		if( start ) {
			p->urm = start->urm;
			start->urm = p;
			p->info = y;
		}
		else {
			p->urm = NULL;
			p->info = y;
			start = p;
		}
	}
}
int main() {
	freopen("sortaret.in","r",stdin);
	freopen("sortaret.out","w",stdout);
	int n,m,i,y,x;
	scanf("%d%d", &n,&m);
	nod **v; int *gi;
	v = (nod**) calloc (n, sizeof(nod*));
	gi = (int*) calloc (n, sizeof(int));
	for (i = 0; i < n; i++){
		scanf("%d%d",&x,&y); x--;y--;
		adaug(v[x],y);
		gi[y]++;
	}
	
	queue<int> coada;
	for(i = 0; i < n; i++) {
		if ( gi[i] == 0 )
			coada.push(i);
	}
	int t;
	while( !coada.empty() ) {
		t = coada.front();
		coada.pop();
		nod *p = v[t];
		while (p) {
			gi[p->info]--;
			if( gi[p->info] == 0)
				coada.push(p->info);
			p = p->urm;
		}
		printf("%d ", t+1);
	}
}