Cod sursa(job #951388)

Utilizator marialivia16Chiorean Maria Livia marialivia16 Data 20 mai 2013 13:57:56
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 kb
#include <iostream>
#include<vector>
#include<queue>
#include<string>
#include<fstream>
#define lim 50100
using namespace std;
class Topo {
    int n,m,ext[lim],coada[lim];
    //queue<int> coada;
    vector<int> v[lim];
    fstream in,out;
public:
    Topo(string fin, string fout)
    {
        in.open(fin.c_str(), ios::in);
        out.open(fout.c_str(), ios::out);
    }
    ~Topo()
    {
        in.close();
        out.close();
    }
    void init()
    {
        for(int i=1;i<=n;i++)
        {
            ext[i]=0;
        }
    }
    void read()
    {
        int a,b;
        in>>n>>m;
        init();
        for(int i=1;i<=m;i++)
        {
            in>>a>>b;
            v[a].push_back(b);
            ext[b]++;
        }
    }
    void solve()
    {
        for(int i=1;i<=n;i++)
        {
            if(ext[i]==0)
            {
                ++coada[0];
                coada[coada[0]]=i;

            }
        }
        int aux;
        vector<int>::iterator it;
        for(int i=1;i<=n;i++)
        {
            aux=coada[i];
            for(it=v[aux].begin();it<v[aux].end();it++)
            {
                ext[*it]--;
                if(ext[*it]==0)
                {
                    coada[++coada[0]]=*it;
                }
            }
        }
        for(int i=1;i<=n;i++)
            out<<coada[i]<<" ";
    }
};
int main()
{
    Topo X("sortaret.in","sortaret.out");
    X.read();
    X.solve();
    return 0;
}