Cod sursa(job #199713)

Utilizator LuxOccultaRadu Dolea LuxOcculta Data 20 iulie 2008 11:59:20
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
using namespace std;

#include <iostream>
#include <fstream>
const int N=50010;

int *a[N],d[N],sef[N],coada[N],sol[N],nr,n,m;

void bf(){
	int p=0,u=0,i,x,y;
	for(i=1;i<=n;++i)//pun initial in coada pe cei care nu au niciun sef
		if(sef[i]==0)
			coada[u++]=i;
	while(p!=u){
		x=coada[p++];
		sol[++sol[0]]=x;
		for(i=1;i<=a[x][0];++i)//parcurg subordonatii directi ai lui x (fiii)
		{
			y=a[x][i];
			--sef[y];
			if(sef[y]==0)
				coada[u++]=y;
		}
	}
}

int main()
{
	
	ifstream f("sortaret.in");
	ofstream g("sortaret.out");
	int x,y,i;
	f>>n>>m;
	for(i=1;i<=m;++i)
	{
		f>>x>>y;
		++d[x];
	}
	f.close();
	for(i=1;i<=n;++i){
		a[i]=new int[d[i]+1];
		a[i][0]=0;
	}
	ifstream h("sortaret.in");
	h>>n>>m;
	for(i=1;i<=m;++i){
		h>>x>>y;
		++sef[y];
		a[x][++a[x][0]]=y;
	}
	h.close();
	bf();
	for(i=1;i<n;++i)
		g<<sol[i]<<" ";
	g<<sol[n]<<"\n";
	g.close();
	return 0;
}