Cod sursa(job #1856978)

Utilizator nicuHiticas Nicu nicu Data 25 ianuarie 2017 17:49:27
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
// topsort.cpp : Defines the entry point for the console application.
//

//#include "stdafx.h"
#include <fstream>
#include <stack>

unsigned int m, n;
struct nod
{
  nod *urm;
  unsigned int vf;
};

nod* Graph[50001];

void Load()
{
  std::ifstream fin("sortaret.in");
  fin >> n >> m;
  for (unsigned int i = 0; i < m; i++)
  {
    unsigned int x, y;
    fin >> x >> y;
    nod* p = new nod();
    p->vf = y;
    p->urm = Graph[x];
    Graph[x] = p;
  }

  fin.close();
}

bool sel[50001];

std::stack<unsigned int> rez;

void AddStack(int vf)
{
  rez.push(vf);
}

void DFS(unsigned int vf)
{
  sel[vf] = true;
  for (nod* x = Graph[vf]; x; x = x->urm)
    DFS(x->vf);
  AddStack(vf);
}

void TopSort()
{
  for (unsigned int i = 1; i <= n; i++)
    if (!sel[i]) DFS(i);

}

void Print()
{
  std::ofstream fout("sortaret.out");
  while (!rez.empty())
  {
    fout << rez.top() << " ";
    rez.pop();
  }
  fout.close();
}


int main()
{
  Load();
  TopSort();
  Print();
  return 0;
}