Cod sursa(job #964103)

Utilizator TripluYOlteanu Costin TripluY Data 20 iunie 2013 05:46:52
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 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;
        --x_nou;
        --y_nou;
        graf[x_nou].push_back(y_nou);
        ++contor[y_nou];
    }
    f.close();
    ofstream g("sortaret.out");
    for(i=0;i<n;++i)
        if(!contor[i])
        {
            coada.push(i);
            g<<i+1<<" ";
        }
    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+1<<" ";
            }
        }
        coada.pop();
    }
    g.close();
    return 0;
}