Cod sursa(job #950350)

Utilizator mihai.agapeMihai Agape mihai.agape Data 16 mai 2013 17:03:06
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <fstream>
#include <list>
#include <vector>
using namespace std;

typedef vector<list<int>> t_g;
int n;
t_g g;
vector<bool> visited;
list<int> sol;

void read()
{
  int m, s, d;
  ifstream fin("sortaret.in");

  fin>>n>>m;
  g = t_g(n+1);
  visited = vector<bool>(n+1, false);
  while(m--)
  {
    fin>>s>>d;
    g[s].push_back(d);
  }

  fin.close();
}

void df(int f)
{
  visited[f]=true;
  for(auto s : g[f])
    if(!visited[s])
      df(s);
  sol.push_front(f);
}

void solve()
{
  for(int i=1; i<=n; ++i)
    if(!visited[i])
      df(i);
}

void write()
{
  ofstream fout("sortaret.out");

  for(auto n : sol)
    fout<<n<<" ";

  fout.close();
}

int main()
{
  read();
  solve();
  write();

  return 0;
}