Cod sursa(job #921718)

Utilizator Mr2peuMaxim Valentin-Constantin Mr2peu Data 21 martie 2013 11:28:10
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.12 kb
/*

*/

#include <iostream>
#include <fstream>
#include <vector>

using namespace std;


fstream f("sortaret.in", ios::in);
fstream g("sortaret.out", ios::out);

class graf
{
    int n, m;                           // n=nr noduri ;; m=nr muchii
	int grad[10000], coada[10000];            //vector de tip int declarat static
    vector <int> vecini[50100];            //vector de tip int declarat in heap

	void citire();

	void rezolvare();

	void afisare();
	
public:
	graf()
	{
		coada[0]=0;
	
	    for (int i=1;i<=100;i++)
	    {
			grad[i]=0;
	    } 

	}

	void apel_citire()
	{
		citire();
	}

	void apel_rezolvare()
	{
		rezolvare();
	}

	void apel_afisare()
	{
		afisare();
	}

	~graf()
	{
		cout<<endl<<"Memorie eliberata!"<<endl;
	}

};

void graf::citire()
{
	int a, b;            //variabila face parte din perechea de forma (i,j)
	int i;               //variabila auxiliara pentru parcurgerea for-ului

	//cout<<endl<<"Numarul nodurilor va rog: "; cin>> n;
	//cout<<endl<<"Numarul muchiilor va rog: "; cin>> m;
	
	f >> n;                //citesc numarul liniilor
	f >> m;                //citesc numarul muchiilors

	for(i=1;i<=m;i++)
	{
		//cout<<"N["<<i<<"].i= "; cin>> a;
		//cout<<"N["<<i<<"].j= "; cin>> b;
		f >> a >> b;         //citesc perechea (i,j)
	    vecini[a].push_back(b);
	    grad[b]++;
	}

}

void graf::rezolvare()
{
	int i,j;             //variabila auxiliara pentru parcurgerea in for

	for (i = 1; i <= n; i++)
		if (grad[i] == 0)
			coada[ ++coada[0] ] = i;

	for(j=1;j<=n;j++)
	{
		i=coada[j];
		for(vector <int>::iterator it=vecini[i].begin();it!=vecini[i].end();++it)
		{--grad[*it];
             if(grad[*it]==0)
	             coada[++coada[0]]=*it;
        }
	}

}

void graf::afisare()
{
	int i;           //variabila auxiliara pentru parcurgerea in for

	for(i=1;i<=n;i++)
		//cout<<coada[i]<<" ";
		g << coada[i] << " ";

	cout<<endl;
}

int main()
{
	graf TOP;       //obiect de tip graf pentru apelarea functiilor clasei

	TOP.apel_citire();
	TOP.apel_rezolvare();
	TOP.apel_afisare();

	system("PAUSE");
}