Cod sursa(job #255863)

Utilizator mihnea_andreiMihnea Andrei mihnea_andrei Data 10 februarie 2009 20:05:09
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb
#include<fstream> 
#include<iostream>
#define b 50010 
using namespace std; 
int d[b],n,m,s,*a[b],nrs[b];
ofstream out ("sortaret.out"); 
void citire () 
{
	ifstream in ("sortaret.in");
	int x,y;
	//cout<<"citesc\n";
	in>>n>>m; 
	while (m--) 
	{
		in>>x>>y; 
		d[x]++;
	} 
	in.close (); 
	//cout<<"aloc\n";
	for(int i=1;i<=n;i++) 
	{ 
		a[i]=new int[1+d[i]]; 
		a[i][0]=0;
	}
	ifstream in2("sortaret.in"); 
	//cout<<"citesc din nou\n";
	in2>>n>>m;
	while (m--)
	{
		in2>>x>>y; 
		//cout<<"am citit "<<x<<","<<y<<endl;
		a[x][++a[x][0]]=y; 
		nrs[y]++;
	}
	//cout<<"am terminat de citit\n";
	in2.close (); 
}
/*
void verificare ()
{
	for(int i=1;i<=n;i++)
	{
		cout<<"vecinii lui "<<i<<": ";
		for(int j=1;j<=a[i][0];j++) 
			cout<<a[i][j]<<" ";
		cout<<endl;
	}
}
*/

void bfs () 
{ 
	int p=0,u=0,i,x,y,coada[b]; 
	for(i=1;i<=n;i++)
		if(nrs[i]==0)
		{
			coada[u++]=i;
			//cout<<"am bagat in coada "<<i<<endl;
			out<<i<<" ";
		}
	while(p!=u) 
	{ 
		x=coada[p++]; 
		//cout<<"scot din coada "<<x<<endl;
		for(i=1;i<=a[x][0];i++) 
		{
			y=a[x][i];
			--nrs[y];
			if(nrs[y]==0)
			{
				out<<y<<" ";
				coada[u++]=y;
				//cout<<"bag in coada "<<y<<endl;
			}			
		}
	}
}  

/*void afisare ()
{
	for(int i=1;i<=n;i++) 
		out<<d[i]<<" "; 	
}
*/

int main ()
{ 
	citire ();
	bfs ();
	out.close ();
	return 0;
}