Cod sursa(job #1438197)

Utilizator sunt_emoSunt emo sunt_emo Data 19 mai 2015 11:52:17
Problema Algoritmul Bellman-Ford Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <fstream>
#include <vector>
#include <list>

bool bfs(const std::vector<std::vector<int> > &graph, int node, std::list<int> &path, std::vector<int> &flags)
{
  if (flags[node] == 2)
    return false;
  path.push_back(node);
  if (flags[node] == 1)
  {
    while (path.front() != node)
      path.pop_front();
    return true;
  }
  flags[node] = 1;
  for (int i = 0; i < static_cast<int>(graph[node].size()); i++)
  {
    if (bfs(graph, graph[node][i], path, flags))
      return true;
  }
  flags[node] = 2;
  path.pop_back();
  return false;
}

int main()
{
  std::ifstream in("gcycle.in");
  int N, M;
  in >> N >> M;
  std::vector<std::vector<int> > graph(N, std::vector<int>());
  for (int i = 0; i < M; i++)
  {
    int x, y, z;
    in >> x >> y;
    graph[x - 1].push_back(y - 1);
  }
  std::vector<int> flags(N, 0);
  std::list<int> path;
  for (int i = 0; i < N; i++)
    if (bfs(graph, i, path, flags))
      break;
  std::ofstream out("gcycle.out");
  if (path.size() == 0)
  {
    out << "0\n";
    return 0;
  }
  out << path.size() << '\n';
  for (std::list<int>::const_iterator it = path.begin(); it != path.end(); ++it)
    out << (*it) + 1 << ' ';
  out << '\n';
}