Cod sursa(job #964102)

Utilizator TripluYOlteanu Costin TripluY Data 20 iunie 2013 05:42:49
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <fstream>
#include <vector>
#include <queue>

#define N_MAX 50000

using namespace std;

int contor[N_MAX];
vector <int> graf[N_MAX];

int main()
{
    ifstream f("sortaret.in");
    int n,m,x_nou,y_nou;
    queue <int> coada;
    f>>n>>m;
    int i;
    for(i=0;i<m;i++)
    {
        f>>x_nou>>y_nou;
        graf[x_nou-1].push_back(y_nou-1);
        ++contor[y_nou-1];
    }
    f.close();
    ofstream g("sortaret.out");
    for(i=0;i<n;++i)
        if(!contor[i])
        {
            coada.push(i);
            g<<i<<" ";
        }
    int x;
    vector <int>::iterator it;
    while(!coada.empty())
    {
        x = coada.front();
        for(it = graf[x].begin();it != graf[x].end();++it)
        {
            --contor[*it];
            if(!contor[*it])
            {
                coada.push(*it);
                g<<*it<<" ";
            }
        }
        coada.pop();
    }
    g.close();
    return 0;
}