Cod sursa(job #922093)

Utilizator Mr2peuMaxim Valentin-Constantin Mr2peu Data 21 martie 2013 22:07:24
Problema Sortare topologica Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 2.44 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[50000];            //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]++;
    }
 
	f.close();
}
 
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] << " ";
    g.close();
    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");
}