Pagini recente » Cod sursa (job #1350550) | Cod sursa (job #1278544) | Cod sursa (job #2047289) | Monitorul de evaluare | Cod sursa (job #921718)
Cod sursa(job #921718)
/*
*/
#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");
}