Cod sursa(job #1753245)

Utilizator lucian666Vasilut Lucian lucian666 Data 6 septembrie 2016 10:51:42
Problema Sortare topologica Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb


#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;
ofstream out("sortaret.out");

#define dim 50000
#define pb push_back

vector < int > Gr[dim];
queue < int > Q;

int de[dim];
int n,m;
vector < int > sol;

void read();
void topo();
void write();
int main()
{

    read();
    topo();
    write();

    return 0;
}

void read()
{
    ifstream in("sortaret.in");
    in >> n >> m;
    for(int x,y; m; --m)
    {
        in >> x >> y;
        Gr[x].pb(y);
        ++de[y];
    }

    for(int i = 1 ; i<=n; ++i)
    {
        if(!de[i])
        {
            Q.push(i);
        }
    }
}

void topo()
{
    while(!Q.empty())
    {
        int root = Q.front();
        Q.pop();
        sol.pb(root);
        for(vector <int>::iterator I = Gr[root].begin(); I!= Gr[root].end(); ++I)
        {
            --de[*I];
            if(de[*I] == 0)
            {
                Q.push(*I);
            }
        }
    }
}

void write()
{
    for(int i = 0; i < sol.size(); ++i)
    {
        out << sol[i] << " ";
    }
}