Seminar6

// Graph.hpp
#pragma once

#include <vector>

struct IGraph {
  virtual ~IGraph() {}

  // Добавление ребра от from к to.
  virtual void AddEdge(int from, int to) = 0;

  virtual size_t VerticesCount() const  = 0;

  virtual std::vector<int> FindAllAdjacentIn(int vertex) const = 0;
  virtual std::vector<int> FindAllAdjacentOut(int vertex) const = 0;
};


// ListGraph.hpp
#pragma once

#include "Graph.hpp"

class ListGraph : public IGraph {
 public:
  explicit ListGraph(size_t vertices_count);

  // Добавление ребра от from к to.
  void AddEdge(int from, int to) override;

  size_t VerticesCount() const override { return childs_.size(); }

  std::vector<int> FindAllAdjacentIn(int vertex) const override;
  std::vector<int> FindAllAdjacentOut(int vertex) const override;

 private:
  // Списки смежности
  std::vector<std::vector<int>> childs_;  // Исходящие ребра
  std::vector<std::vector<int>> parents_;  // Входящие
};


// ListGraph.cpp
#include "ListGraph.hpp"

ListGraph::ListGraph(size_t vertices_count) : childs_(vertices_count), parents_(vertices_count) {}

void ListGraph::AddEdge(int from, int to) {
  childs_[from].push_back(to);
  parents_[to].push_back(from);
}

std::vector<int> ListGraph::FindAllAdjacentIn(int vertex) const {
  return parents_[vertex];
}

std::vector<int> ListGraph::FindAllAdjacentOut(int vertex) const {
  return childs_[vertex];
}


// main.cpp
#include <iostream>
#include <vector>

#include "ListGraph.hpp"

class Furniture {
 public:
  virtual int Calories() const = 0;
};

class Sofa : public Furniture {
 public:
  int Calories() const final { return 1000000; }
};

class IronChair : public Furniture {
 public:
  int Calories() const final { return 0; }
};

void Burn(Furniture& f) {
  std::cout << "It's fire. Your room was heated on " << f.Calories() << " cals." << std::endl;
}

int main1() {
  std::vector<Furniture*> furnitures;
  Sofa s;
  furnitures.push_back(&s);
  IronChair i;
  furnitures.push_back(&i);
  for (auto& f : furnitures) Burn(*f);

  IronChair x;
  Burn(x);
  return 0;
}

void DFS(int v, const IGraph& graph, std::vector<bool>& visited,
         std::vector<std::pair<int, int>>& times, int& time) {
  times[v].first = time;

  visited[v] = true;
  std::cout << v << " ";
  for (int x : graph.FindAllAdjacentOut(v)) {
    if (!visited[x]) {
      DFS(x, graph, visited, times, time);
    }
  }

  times[v].second = ++time;
}

std::vector<std::pair<int, int>> DFS(const IGraph& g) {
  int time = 0;
  std::vector<std::pair<int, int>> times(g.VerticesCount());
  std::vector<bool> visited(g.VerticesCount(), false);
/*  auto l = [&visited, &g] (int v, auto& l) {
    visited[v] = true;
    std::cout << v << " ";
    for (int x : g.FindAllAdjacentOut(v)) {
      if (!visited[x]) l(x, l);
    }
  };*/
  for (int i = 0; i < visited.size(); ++i)
    if (!visited[i]) {
      // l(i, l);
      DFS(i, g, visited, times, time);
    }
  return times;
}

int main() {
  ListGraph lg(9);
  lg.AddEdge(6, 0);
  lg.AddEdge(3, 4);
  lg.AddEdge(8, 4);
  lg.AddEdge(7, 8);
  lg.AddEdge(4, 7);
  lg.AddEdge(3, 2);
  lg.AddEdge(2, 1);
  lg.AddEdge(2, 5);
  lg.AddEdge(1, 5);
  lg.AddEdge(5, 7);

  std::vector<std::pair<int, int>> times = DFS(lg);
  for (int i = 0; i < lg.VerticesCount(); ++i) {
    std::cout << i << ": " << times[i].first << " " << times[i].second << std::endl;
  }
  return 0;
}