mrlantan

Untitled

Dec 2nd, 2020
547
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <map>
  4. #include <vector>
  5. #include <utility>
  6.  
  7. //std::vector<std::vector<int>> graph;
  8. //std::vector<std::vector<int>> reversed_graph;
  9. //std::vector<std::pair<int, int>> t_out;
  10. //std::vector<std::pair<int, int>> edges;
  11. //std::vector<bool> color_good;
  12. //std::vector<int> color;
  13. //
  14. //int cur_time = 0;
  15. //int cur_color = 1;
  16.  
  17. typedef std::vector<std::vector<int>> AdjacencyList;
  18. typedef std::vector<std::pair<int, int>> EdgeList;
  19.  
  20. struct GameResult {
  21.     int left_player, right_player;
  22.     int result;
  23. };
  24.  
  25. struct InputData {
  26.     int employee_count;
  27.     std::vector<GameResult> games;
  28. };
  29.  
  30. class Graph {
  31. public:
  32.     explicit Graph(int vertex_count) : adjacency_list_(vertex_count + 1) {
  33.     }
  34.  
  35.     void AddEdge(int from, int to) {
  36.         adjacency_list_[from].push_back(to);
  37.     }
  38.  
  39.     const std::vector<int>& GetNeighbours(int vertex) const {
  40.         return adjacency_list_[vertex];
  41.     }
  42.  
  43.     int VertexCount() const {
  44.         return static_cast<int>(adjacency_list_.size() - 1);
  45.     }
  46.  
  47. private:
  48.     AdjacencyList adjacency_list_;
  49. };
  50.  
  51. class VisitorBase {
  52. public:
  53.     void DiscoverVertex(const Graph& graph, int vertex) const {
  54.     }
  55.  
  56.     void FinishVertex(const Graph& graph, int vertex) const {
  57.     }
  58. };
  59.  
  60. class ForwardDFSVisitor : public VisitorBase {
  61. public:
  62.     ForwardDFSVisitor(std::vector<int>* exit_time, int* exit_time_counter)
  63.         : exit_time_(exit_time), exit_time_counter_(exit_time_counter) {
  64.     }
  65.  
  66.     void FinishVertex(const Graph& graph, int vertex) const {
  67.         exit_time_->operator[](vertex) = (*exit_time_counter_)++;
  68.     }
  69.  
  70. private:
  71.     int* exit_time_counter_;
  72.     std::vector<int>* exit_time_;
  73. };
  74.  
  75. class BackwardDFSVisitor : public VisitorBase {
  76. public:
  77.     BackwardDFSVisitor(std::vector<int>* strongly_connected_component_id, int* id_counter)
  78.         : strongly_connected_component_id_(strongly_connected_component_id),
  79.         id_counter_(id_counter) {
  80.     }
  81.  
  82.     void DiscoverVertex(const Graph& graph, int vertex) const {
  83.         strongly_connected_component_id_->operator[](vertex) = *id_counter_;
  84.     }
  85.  
  86. private:
  87.     std::vector<int>* strongly_connected_component_id_;
  88.     int* id_counter_;
  89. };
  90.  
  91. InputData ReadGameResultsFromInput(std::istream& input) {
  92.     int employee_count, games_count;
  93.     input >> employee_count >> games_count;
  94.  
  95.     std::vector<GameResult> game_results;
  96.     for (int i = 0; i < games_count; ++i) {
  97.         int first_player, second_player, result;
  98.         input >> first_player >> second_player >> result;
  99.         game_results.push_back({first_player, second_player, result});
  100.     }
  101.  
  102.     return {employee_count, game_results};
  103. }
  104.  
  105. Graph CreateRelationshipsGraph(const InputData& input_data) {
  106.     Graph graph(input_data.employee_count);
  107.  
  108.     for (const auto& game : input_data.games) {
  109.         if (game.result == 1) {
  110.             graph.AddEdge(game.left_player, game.right_player);
  111.         } else if (game.result == 2) {
  112.             graph.AddEdge(game.right_player, game.left_player);
  113.         }
  114.     }
  115.  
  116.     return graph;
  117. }
  118.  
  119. Graph Transpose(const Graph& graph) {
  120.     Graph reversed_graph(graph.VertexCount());
  121.     for (int i = 1; i <= graph.VertexCount(); ++i) {
  122.         const auto& adjacent_vertices = graph.GetNeighbours(i);
  123.         for (size_t j = 0; j < adjacent_vertices.size(); ++j) {
  124.             reversed_graph.AddEdge(adjacent_vertices[j], i);
  125.         }
  126.     }
  127.  
  128.     return reversed_graph;
  129. }
  130.  
  131. template <typename Graph, typename Visitor>
  132. void DepthFirstSearch(const Graph& graph, Visitor visitor, int vertex, std::vector<int>& color) {
  133.     color[vertex] = 1;
  134.     visitor.DiscoverVertex(graph, vertex);
  135.  
  136.     for (size_t i = 0; i < graph.GetNeighbours(vertex).size(); ++i) {
  137.         int to = graph.GetNeighbours(vertex)[i];
  138.         if (!color[to]) {
  139.             DepthFirstSearch(graph, visitor, to, color);
  140.         }
  141.     }
  142.  
  143.     visitor.FinishVertex(graph, vertex);
  144. }
  145.  
  146.  
  147. std::vector<int> TopologicalSort(const Graph& graph) {
  148.     std::vector<int> color(graph.VertexCount() + 1, 0);
  149.     std::vector<int> exit_times(graph.VertexCount() + 1, 0);
  150.     int time_counter = 1;
  151.  
  152.     ForwardDFSVisitor forward_dfs_visitor(&exit_times, &time_counter);
  153.  
  154.     for (int i = 1; i <= graph.VertexCount(); ++i) {
  155.         if (color[i] == 0) {
  156.             DepthFirstSearch(graph, forward_dfs_visitor, i, color);
  157.         }
  158.     }
  159.  
  160.     std::vector<std::pair<int, int>> exit_time_and_index(graph.VertexCount());
  161.     for (size_t i = 0; i < exit_times.size(); ++i) {
  162.         exit_time_and_index.emplace_back(exit_times[i + 1], static_cast<int>(i));
  163.     }
  164.  
  165.     std::sort(exit_time_and_index.begin(), exit_time_and_index.end(),
  166.               [](auto lhs, auto rhs) {
  167.                   return lhs > rhs;
  168.               });
  169.  
  170.     std::vector<int> topologically_sorted_vertices(graph.VertexCount() + 1);
  171.     for (size_t i = 0; i < topologically_sorted_vertices.size(); ++i) {
  172.         topologically_sorted_vertices[i] = exit_time_and_index[i].second;
  173.     }
  174.  
  175.     return topologically_sorted_vertices;
  176. }
  177.  
  178. std::pair<std::vector<int>, int> FindStronglyConnectedComponents(const Graph& graph) {
  179.     auto transposed_graph = Transpose(graph);
  180.     auto topologically_sorted_vertices = TopologicalSort(graph);
  181.     std::vector<int> strongly_connected_component_id(graph.VertexCount() + 1, 0);
  182.     std::vector<int> color(graph.VertexCount(), 0);
  183.     int id_counter = 1;
  184.  
  185.     BackwardDFSVisitor backward_dfs_visitor(&strongly_connected_component_id, &id_counter);
  186.  
  187.     for (size_t i = 0; i < topologically_sorted_vertices.size(); ++i) {
  188.         if (color[topologically_sorted_vertices[i]] == 0) {
  189.             DepthFirstSearch(graph, backward_dfs_visitor, topologically_sorted_vertices[i], color);
  190.             ++id_counter;
  191.         }
  192.     }
  193.  
  194.     return std::make_pair(strongly_connected_component_id, id_counter - 1);
  195. }
  196.  
  197. std::vector<int> FindStronglyConnectedComponentsSizes(const std::vector<int>& scc_id, int total_count) {
  198.     std::vector<int> result(total_count + 1, 0);
  199.     for (size_t i = 1; i < scc_id.size(); ++i) {
  200.         ++result[scc_id[i]];
  201.     }
  202.  
  203.     return result;
  204. }
  205.  
  206. std::vector<int> FindOuterStronglyConnectedComponents(const Graph& graph, const std::vector<int>& scc_id,
  207.                                                       int total_count) {
  208.     std::vector<bool> outer_component(total_count + 1, true);
  209.     for (int i = 1; i < graph.VertexCount(); ++i) {
  210.         for (auto j : graph.GetNeighbours(i)) {
  211.             if (scc_id[i] != scc_id[j]) {
  212.                 outer_component[scc_id[j]] = false;
  213.             }
  214.         }
  215.     }
  216.  
  217.     std::vector<int> result;
  218.  
  219.     for (int i = 1; i <= total_count; ++i) {
  220.         if (outer_component[i]) {
  221.             result.push_back(i);
  222.         }
  223.     }
  224.  
  225.     return result;
  226. }
  227.  
  228. int FindMinimalOuterSCCSize(const std::vector<int>& scc_sizes, std::vector<int> outer_scc_ids) {
  229.     int result = -1;
  230.     for (auto outer_scc_id : outer_scc_ids) {
  231.         if (result == -1 || scc_sizes[outer_scc_id] < result) {
  232.             result = scc_sizes[outer_scc_id];
  233.         }
  234.     }
  235.  
  236.     return result;
  237. }
  238.  
  239. int main() {
  240.     std::ios_base::sync_with_stdio(false);
  241.     std::cin.tie(nullptr);
  242.  
  243.     InputData input_data = ReadGameResultsFromInput(std::cin);
  244.     Graph graph = CreateRelationshipsGraph(input_data);
  245.     auto strongly_connected_component_id_and_total_count =
  246.             FindStronglyConnectedComponents(graph);
  247.  
  248.     auto scc_id = std::move(strongly_connected_component_id_and_total_count.first);
  249.     auto total_count = strongly_connected_component_id_and_total_count.second;
  250.  
  251.     auto scc_sizes = FindStronglyConnectedComponentsSizes(scc_id, total_count);
  252.     auto outer_scc_ids = FindOuterStronglyConnectedComponents(graph, scc_id, total_count);
  253.     auto minimal_outer_scc_size = FindMinimalOuterSCCSize(scc_sizes, outer_scc_ids);
  254.  
  255.     std::cout << graph.VertexCount() - minimal_outer_scc_size + 1 << std::endl;
  256.  
  257.     return 0;
  258. }
  259.  
RAW Paste Data