Seminar7

// Здесь только main.cpp.
// ListGraph.hpp - как в предыдущем семинаре.

#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>

#include "ListGraph.hpp"

void BFS(const IGraph& g) {
  std::vector<bool> visited(g.VerticesCount());

  for (int i = 0; i < g.VerticesCount(); ++i) {
    if (!visited[i]) {
      std::queue<int> q;
      q.push(i);
      visited[i] = true;
      while (!q.empty()) {
        int current = q.front();
        q.pop();
        std::cout << current << " ";
        for (int w: g.FindAllAdjacentOut(current)) {
          if (!visited[w]) {
            q.push(w);
            visited[w] = true;
          }
        }
      }
    }
  }
  std::cout << std::endl;
}

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

  BFS(lg);

  std::cout << "Hello, World!" << std::endl;
  return 0;
}

void ReverseDFS(const IGraph& g, int v, std::vector<int>& leaves, std::vector<bool>& visited) {
  static int time = 0;
  visited[v] = true;
  for (int u : g.FindAllAdjacentIn(v)) {
    if (!visited[u])
      ReverseDFS(g, u, leaves, visited);
  }
  leaves[v] = ++time;
}

std::vector<int> MainReverseDFS(const IGraph& g) {
  std::vector<int> leaves(g.VerticesCount());
  std::vector<bool> visited(g.VerticesCount());
  for (int v = 0; v < g.VerticesCount(); ++v) {
    if (!visited[v]) {
      ReverseDFS(g, v, leaves, visited);
    }
  }
  return leaves;
}

void DFS(const IGraph& g, int v, std::vector<bool>& visited, std::vector<int>& components, int component) {
  visited[v] = true;
  components[v] = component;
  for (int u : g.FindAllAdjacentOut(v)) {
    if (!visited[u])
      DFS(g, u, visited, components, component);
  }
}

std::vector<int> MainDFS(const IGraph& g, const std::vector<int>& leaves) {
  std::vector<std::pair<int, int>> leave_and_vertices;
  for (int i = 0; i < leaves.size(); ++i) leave_and_vertices.push_back({leaves[i], i});
  std::sort(leave_and_vertices.rbegin(), leave_and_vertices.rend());

  std::vector<int> components(g.VerticesCount());
  std::vector<bool> visited(g.VerticesCount());

  int component = 0;
  for (auto& [leave, v] : leave_and_vertices) {
    if (!visited[v]) {
      DFS(g, v, visited, components, component);
    }
    ++component;
  }
  return components;
}

ListGraph Condensation(const IGraph& g) {
  // Соберем соответствие номер вершины -> номер КСС.
  // Алгоритм Косарайю.
  // Собираем времена выхода.
  std::vector<int> leaves = MainReverseDFS(g);
  // Запускаем DFS в порядке убывания leaves.
  std::vector<int> components = MainDFS(g, leaves);

  // Создадим граф конденсации и заполним его.
  ListGraph condensation();
  return condensation;
}

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

  ListGraph condensation = Condensation(lg);

  std::cout << "Hello, World!" << std::endl;
  return 0;
}