RetroAnalysis

#include <iostream>
#include <vector>

enum class Type {
  Neutral,
  Loose,
  Win
};

std::string ToString(Type type) {
  switch (type) {
    case Type::Neutral:
      return "N";
    case Type::Loose:
      return "L";
    case Type::Win:
      return "W";
  }
}

class Game {
 public:
  explicit Game(std::vector<std::vector<int>> incomes_) : incomes(std::move(incomes_)) {}

  std::vector<Type> GetTypes();

 private:
  std::vector<std::vector<int>> incomes;
  std::vector<Type> types;

  void RunRetroAnalysis();
  void RetroDFS(int vertex, std::vector<bool>& visited, std::vector<int>& degrees);
};

std::vector<Type> Game::GetTypes() {
  if (types.empty()) RunRetroAnalysis();
  return types;
}

// Ретроспективный анализ. Заполняет type.
void Game::RunRetroAnalysis() {
  types = std::vector<Type>(incomes.size(), Type::Neutral);

  std::vector<bool> visited(incomes.size(), false);
  std::vector<int> degrees(incomes.size(), 0);
  for (int to = 0; to < incomes.size(); ++to) {
    for (int from : incomes[to]) {
      ++degrees[from];
    }
  }

  RetroDFS(0, visited, degrees);
}

void Game::RetroDFS(int vertex, std::vector<bool>& visited, std::vector<int>& degrees) {
  visited[vertex] = true;
  for (int from : incomes[vertex]) {
    if (visited[from]) continue;
    if (types[vertex] == Type::Loose ) {
      types[from] = Type::Win;
    } else if(--degrees[from] == 0) {
      types[from] = Type::Loose;
    } else {
      continue;
    }
    RetroDFS(from, visited, degrees);
  }
}

int main() {
  Game game({{1, 2, 3}, {4}, {4}, {4}, {5}, {}});
  const auto types = game.GetTypes();

  for (Type type : types) {
    std::cout << ToString(type) << " ";
  }
  std::cout << std::endl;
  return 0;
}