Cod sursa(job #864087)

Utilizator cr4zym4nAdrian Necula cr4zym4n Data 24 ianuarie 2013 17:40:33
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.57 kb
#include<fstream>
#include<bitset>
using namespace std;
ifstream f("sortaret.in");
ofstream g("sortaret.out");
int n,m,a,b,p,u;
bitset<50001>x[50001];
short c[50001],d[50001],viz[50001];
int main(){
	f>>n>>m;
	for(int i=1;i<=m;++i){
		f>>a>>b;
		x[a][b]=1;
		d[b]++;
	}
	for(int i=1;i<=n;++i)
		if(d[i]==0){
			c[++u]=i;
			viz[i]=1;
		}
	for(int i=1;i<=n;++i){
		a=c[i];
		for(int j=1;j<=n;++j){
			if(x[a][j] && viz[j]==0){
				d[j]--;
				if(d[j]==0) c[++u]=j;
			}
		}
	}
	for(int i=1;i<=n;++i)
		g<<c[i]<<' ';
	g<<'\n';
	g.close();
	return 0;
}