vadimk772336

ревью компания

May 21st, 2022 (edited)
789
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. namespace
  5. {
  6. constexpr int g_uninitialized = -1;
  7. constexpr int shift_to_idx = -1;
  8. } // namespace
  9.  
  10. struct vertex
  11. {
  12.     std::vector<int> m_adj_list;
  13.     bool m_isvisited = false;
  14.     int m_comp_num = g_uninitialized;
  15.     int m_t_out = g_uninitialized;
  16. };
  17.  
  18. struct comp_info
  19. {
  20.     bool m_ishated = false;
  21.     int m_comp_size = 0;
  22. };
  23.  
  24.  
  25. class Graph
  26. {
  27.     std::vector<vertex> m_graph;
  28.     int m_size = 0;
  29.  
  30. public:
  31.     explicit Graph(const int size);
  32.     void addEdge(const int i, const int j);
  33.     void DFS(const int v_index, int& current_t_out);
  34.     void DFS_reversed(const int v_index, const int current_comp_num);
  35.     std::vector<int> get_t_out_array();
  36.     std::vector<struct comp_info> get_comp_info_array(const int count_comp);
  37.     int get_comp_num(const int v_index);
  38. };
  39.  
  40.  
  41. Graph::Graph(const int size)
  42. {
  43.     this->m_graph.resize(size);
  44.     this->m_size = size;
  45. }
  46.  
  47. int Graph::get_comp_num(const int v_index)
  48. {
  49.     return m_graph[v_index].m_comp_num;
  50. }
  51.  
  52. void Graph::addEdge(const int i, const int j)
  53. {
  54.     m_graph[i].m_adj_list.push_back(j);
  55. }
  56.  
  57. void Graph::DFS(const int v_index, int& current_t_out)
  58. {
  59.  
  60.     if (!m_graph[v_index].m_isvisited)
  61.     {
  62.         m_graph[v_index].m_isvisited = true;
  63.  
  64.         for (int u_index : m_graph[v_index].m_adj_list)
  65.         {
  66.             DFS(u_index, current_t_out);
  67.         }
  68.  
  69.         m_graph[v_index].m_t_out = current_t_out;
  70.         ++current_t_out;
  71.     }
  72. }
  73.  
  74. void Graph::DFS_reversed(const int v_index, const int current_comp_num)
  75. {
  76.  
  77.     if (!m_graph[v_index].m_isvisited)
  78.     {
  79.         m_graph[v_index].m_isvisited = true;
  80.  
  81.         for (int u_index : m_graph[v_index].m_adj_list)
  82.         {
  83.             DFS_reversed(u_index, current_comp_num);
  84.         }
  85.  
  86.         m_graph[v_index].m_comp_num = current_comp_num;
  87.     }
  88. }
  89.  
  90.  
  91. std::vector<int> Graph::get_t_out_array()
  92. {
  93.  
  94.     for (int t_out = 0, v_index = 0; v_index < this->m_size; ++v_index)
  95.     {
  96.         DFS(v_index, t_out);
  97.     };
  98.  
  99.     std::vector<int> t_out(this->m_size);
  100.  
  101.     for (int i = 0; i < this->m_size; ++i)
  102.     {
  103.         t_out[this->m_size - m_graph[i].m_t_out - 1] = i;
  104.     }
  105.  
  106.     return t_out;
  107. }
  108.  
  109. std::vector<struct comp_info> Graph::get_comp_info_array(const int count_comp)
  110. {
  111.  
  112.     std::vector<comp_info> comp_info_array(count_comp);
  113.  
  114.     for (int comp_num, i = 0; i < this->m_size; ++i)
  115.     {
  116.         comp_num = m_graph[i].m_comp_num;
  117.         for (int u_index : m_graph[i].m_adj_list)
  118.         {
  119.             if (comp_num != m_graph[u_index].m_comp_num)
  120.             {
  121.                 comp_info_array[comp_num].m_ishated = true;
  122.                 break;
  123.             }
  124.         }
  125.         ++comp_info_array[comp_num].m_comp_size;
  126.     }
  127.  
  128.     return comp_info_array;
  129. }
  130.  
  131. void build_graphs(Graph& graph, Graph& graph_reversed, const int count_games)
  132. {
  133.     for (int player_one, player_two, result, i = 0; i < count_games; ++i)
  134.     {
  135.         std::cin >> player_one >> player_two >> result;
  136.  
  137.         if (result == 1)
  138.         {
  139.             graph.addEdge(player_one + shift_to_idx, player_two + shift_to_idx);
  140.             graph_reversed.addEdge(player_two + shift_to_idx, player_one + shift_to_idx);
  141.         }
  142.         if (result == 2)
  143.         {
  144.             graph.addEdge(player_two + shift_to_idx, player_one + shift_to_idx);
  145.             graph_reversed.addEdge(player_one + shift_to_idx, player_two + shift_to_idx);
  146.         }
  147.     }
  148. }
  149.  
  150. int get_count_comp(Graph& graph_reversed, const std::vector<int>& t_out_array)
  151. {
  152.     int count_comp = 0;
  153.     for (int t_out : t_out_array)
  154.     {
  155.         if (graph_reversed.get_comp_num(t_out) == g_uninitialized)
  156.         {
  157.             graph_reversed.DFS_reversed(t_out, count_comp);
  158.             ++count_comp;
  159.         }
  160.     }
  161.  
  162.     return count_comp;
  163. }
  164.  
  165. int get_min_comp_size(
  166.     int num_people, const std::vector<comp_info>& comp_info_array, const int count_comp)
  167. {
  168.  
  169.     for (int i = 0; i < count_comp; ++i)
  170.     {
  171.         if (!comp_info_array[i].m_ishated && comp_info_array[i].m_comp_size < num_people)
  172.         {
  173.             num_people = comp_info_array[i].m_comp_size;
  174.         }
  175.     }
  176.  
  177.     return num_people;
  178. }
  179.  
  180. int main()
  181. {
  182.  
  183.     int num_people, count_games;
  184.     std::cin >> num_people >> count_games;
  185.  
  186.     Graph graph(num_people);
  187.     Graph graph_reversed(num_people);
  188.  
  189.     build_graphs(graph, graph_reversed, count_games);
  190.  
  191.     std::vector<int> t_out_array = graph.get_t_out_array();
  192.  
  193.     int count_comp = get_count_comp(graph_reversed, t_out_array);
  194.  
  195.     std::vector<comp_info> comp_info_array = graph_reversed.get_comp_info_array(count_comp);
  196.  
  197.     int min_comp_size = get_min_comp_size(num_people, comp_info_array, count_comp);
  198.  
  199.     std::cout << num_people - min_comp_size + 1;
  200.  
  201.     return 0;
  202. }
  203.  
RAW Paste Data Copied