Cod sursa(job #526906)

Utilizator icepowdahTudor Didilescu icepowdah Data 29 ianuarie 2011 19:27:44
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include <fstream>
using namespace std;

#define NMAX 50000

struct list {
  int id;
  list* next;
};

int N, M;
bool visited[NMAX+1];
list* adj_list[NMAX+1];
list* solutie;
int time;

void readInput();
void dfs(int i);
void printOutput();

int main(void)
{
  readInput();

  for (int i=1;i<=N;i++)
  {
    if (!visited[i]) dfs(i);
  }

  printOutput();

  return 0;
}

void readInput()
{
  int from, to;
  ifstream f("sortaret.in");

  f >> N >> M;
  for (int i=1;i<=M;i++)
  {
    f >> from >> to;    
    list* x = new list;
    x->id = to;
    x->next = adj_list[from];
    adj_list[from] = x;
  }

  f.close();
}

void dfs(int i)
{
  visited[i] = true;  
  list* it = adj_list[i];
  while (it != NULL)
  {
    if (!visited[it->id])
    {
      dfs(it->id);
    }
    it = it->next;
  }
  
  list* newNode = new list;
  newNode->id = i;
  newNode->next = solutie;
  solutie = newNode;
}

void printOutput()
{
  ofstream g("sortaret.out");

  while (solutie != NULL)
  {
    g << solutie->id << " ";
    list* tmp = solutie;
    solutie = solutie->next;
    delete tmp;
  }
  g << "\n";

  g.close();
}