Cod sursa(job #1228644)

Utilizator cdascaluDascalu Cristian cdascalu Data 14 septembrie 2014 20:58:29
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include<iostream>
#include<list>
#include<fstream>
#include<vector>
#include<queue>
#include<string.h>
#include<algorithm>
#define Nmax 50001
using namespace std;

int read(vector<int> G[])
{
    int size, edges, x, y;
    ifstream f("sortaret.in");
    f>>size>>edges;
    while(edges--)
    {
        f>>x>>y;
        G[x].push_back(y);
    }

    return size;
}

void write(const list<int> &sol)
{
    ofstream g("sortaret.out");
    for(auto it = sol.begin(); it != sol.end(); ++it)
        g<<*it<<" ";
    g.close();
}
int main()
{
    int size;
    vector<int> G[Nmax];
    int degree[Nmax];

    size = read(G);

    memset(degree, 0, sizeof(degree));

    for(int i=1;i<=size;++i)
    {
        for(auto it = G[i].begin(); it != G[i].end(); ++it)
            ++degree[*it];
    }

    queue<int> Q;
    list<int> sol;

    for(int i=1;i<=size;++i)
        if(degree[i] == 0)
            Q.push(i);

    while(!Q.empty()){

        int vertex = Q.front();
        Q.pop();
        sol.push_back(vertex);

        for(auto it = G[vertex].begin(); it != G[vertex].end(); ++it)
        {
            --degree[*it];
            if(degree[*it] == 0)
                Q.push(*it);
        }

        G[vertex].erase(G[vertex].begin(), G[vertex].end());
    }

    write(sol);
    return 0;
}