Cod sursa(job #929577)

Utilizator UnforgivenMihai Catalin Botezatu Unforgiven Data 27 martie 2013 09:30:24
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <fstream>
#include <deque>
#include <cstdlib>
#include <vector>

using namespace std;

const static int nmax = 50001;

vector <int> graph[nmax];
int nr_noduri;
int nr_muchii;
bool sel[nmax];
deque <int> lista;


void read_graph()
{
    ifstream input("sortaret.in");
    input >> nr_noduri >> nr_muchii;

    for (int i =0;i<nr_muchii ; i++)
    {
        int x , y;
        input >> x >> y;
        graph[x].push_back(y);
    }

    input.close();

}

void DF(int nod)
{
    sel[nod] = true;
    for (int i =0;i<graph[nod].size();i++)
    {
        int next = graph[nod][i];
        if (!sel[next]) DF(next);
    }

    lista.push_front(nod);
}

void print()
{
    ofstream output("sortaret.out");
    for (int i =0;i<lista.size();i++)
    {
        output << lista[i] << " ";
    }
    output.close();
}

int main()
{
    read_graph();
    for (int i = 1;i<=nr_noduri;i++)
    {
        if (!sel[i]) DF(i);
    }
    print();



    return 0;
}