smatskevich

RetroAnalysis

Dec 17th, 2019
130
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. enum class Type {
  5.   Neutral,
  6.   Loose,
  7.   Win
  8. };
  9.  
  10. std::string ToString(Type type) {
  11.   switch (type) {
  12.     case Type::Neutral:
  13.       return "N";
  14.     case Type::Loose:
  15.       return "L";
  16.     case Type::Win:
  17.       return "W";
  18.   }
  19. }
  20.  
  21. class Game {
  22.  public:
  23.   explicit Game(std::vector<std::vector<int>> incomes_) : incomes(std::move(incomes_)) {}
  24.  
  25.   std::vector<Type> GetTypes();
  26.  
  27.  private:
  28.   std::vector<std::vector<int>> incomes;
  29.   std::vector<Type> types;
  30.  
  31.   void RunRetroAnalysis();
  32.   void RetroDFS(int vertex, std::vector<bool>& visited, std::vector<int>& degrees);
  33. };
  34.  
  35. std::vector<Type> Game::GetTypes() {
  36.   if (types.empty()) RunRetroAnalysis();
  37.   return types;
  38. }
  39.  
  40. // Ретроспективный анализ. Заполняет type.
  41. void Game::RunRetroAnalysis() {
  42.   types = std::vector<Type>(incomes.size(), Type::Neutral);
  43.  
  44.   std::vector<bool> visited(incomes.size(), false);
  45.   std::vector<int> degrees(incomes.size(), 0);
  46.   for (int to = 0; to < incomes.size(); ++to) {
  47.     for (int from : incomes[to]) {
  48.       ++degrees[from];
  49.     }
  50.   }
  51.  
  52.   RetroDFS(0, visited, degrees);
  53. }
  54.  
  55. void Game::RetroDFS(int vertex, std::vector<bool>& visited, std::vector<int>& degrees) {
  56.   visited[vertex] = true;
  57.   for (int from : incomes[vertex]) {
  58.     if (visited[from]) continue;
  59.     if (types[vertex] == Type::Loose ) {
  60.       types[from] = Type::Win;
  61.     } else if(--degrees[from] == 0) {
  62.       types[from] = Type::Loose;
  63.     } else {
  64.       continue;
  65.     }
  66.     RetroDFS(from, visited, degrees);
  67.   }
  68. }
  69.  
  70. int main() {
  71.   Game game({{1, 2, 3}, {4}, {4}, {4}, {5}, {}});
  72.   const auto types = game.GetTypes();
  73.  
  74.   for (Type type : types) {
  75.     std::cout << ToString(type) << " ";
  76.   }
  77.   std::cout << std::endl;
  78.   return 0;
  79. }
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×