Cod sursa(job #1703031)

Utilizator marinaflommarina florentina marinaflom Data 16 mai 2016 00:56:05
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

vector <int> G[50010];
vector <int> rez;
int gradInterior[50010];
int N, M;

void Read()
{
    ifstream f("sortaret.in");
    f >> N >> M;
    for (int i = 1; i <= M; ++ i)
    {
        int x, y;
        f >> x >> y;
        G[x].push_back(y);
        gradInterior[y]++;
    }
    f.close();
}

void Solve()
{
    queue <int> Q;
    for(int i = 1; i <= N; ++ i)
        if (gradInterior[i] == 0)
            Q.push(i);
    while(!Q.empty())
    {
        int nodExtras = Q.front();
        Q.pop();
        rez.push_back(nodExtras);
        for (vector<int> :: iterator it = G[nodExtras].begin(); it != G[nodExtras].end(); ++ it)
        {
            gradInterior[*it]--;
            if(gradInterior[*it] == 0)
                Q.push(*it);
        }
    }
}

void Write()
{
    ofstream g("sortaret.out");
    for (vector <int> :: iterator it = rez.begin(); it != rez.end(); ++ it)
        g << *it << " ";
    g << "\n";
    g.close();
}

int main()
{
    Read();
    Solve();
    Write();
    return 0;
}