vadimk772336

Untitled

May 14th, 2022 (edited)
94
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 ishated = false;
  21.     int comp_size = 0;
  22. };
  23.  
  24.  
  25. class Graph
  26. {
  27.     struct vertex* graph;
  28.     int 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.     graph = new vertex[size];
  44.     this->size = size;
  45. }
  46.  
  47. int Graph::get_comp_num(const int v_index)
  48. {
  49.     return graph[v_index].m_comp_num;
  50. }
  51.  
  52. void Graph::addEdge(const int i, const int j)
  53. {
  54.     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 (!graph[v_index].m_isvisited)
  61.     {
  62.         graph[v_index].m_isvisited = true;
  63.  
  64.         for (int u_index : graph[v_index].m_adj_list)
  65.         {
  66.             DFS(u_index, current_t_out);
  67.         }
  68.  
  69.         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 (!graph[v_index].m_isvisited)
  78.     {
  79.         graph[v_index].m_isvisited = true;
  80.  
  81.         for (int u_index : graph[v_index].m_adj_list)
  82.         {
  83.             DFS_reversed(u_index, current_comp_num);
  84.         }
  85.  
  86.         graph[v_index].m_comp_num = current_comp_num;
  87.     }
  88. }
  89.  
  90. std::vector<int> Graph::get_t_out_array()
  91. {
  92.  
  93.     for (int t_out = 0, v_index = 0; v_index < this->size; ++v_index)
  94.     {
  95.         DFS(v_index, t_out);
  96.     };
  97.  
  98.     std::vector<int> t_out(this->size);
  99.  
  100.     for (int i = 0; i < this->size; ++i)
  101.     {
  102.         t_out[this->size - graph[i].m_t_out - 1] = i;
  103.     }
  104.  
  105.     return t_out;
  106. }
  107.  
  108. std::vector<struct comp_info> Graph::get_comp_info_array(const int count_comp)
  109. {
  110.  
  111.     std::vector<comp_info> comp_info_array(count_comp);
  112.  
  113.     for (int comp_num, i = 0; i < this->size; ++i)
  114.     {
  115.         comp_num = graph[i].m_comp_num;
  116.         for (int u_index : graph[i].m_adj_list)
  117.         {
  118.             if (comp_num != graph[u_index].m_comp_num)
  119.             {
  120.                 comp_info_array[comp_num].ishated = true;
  121.                 break;
  122.             }
  123.         }
  124.         ++comp_info_array[comp_num].comp_size;
  125.     }
  126.  
  127.     return comp_info_array;
  128. }
  129.  
  130. void build_graphs(Graph graph, Graph graph_reversed, const int count_games)
  131. {
  132.     for (int player_one, player_two, result, i = 0; i < count_games; ++i)
  133.     {
  134.         std::cin >> player_one >> player_two >> result;
  135.  
  136.         if (result == 1)
  137.         {
  138.             graph.addEdge(player_one + shift_to_idx, player_two + shift_to_idx);
  139.             graph_reversed.addEdge(player_two + shift_to_idx, player_one + shift_to_idx);
  140.         }
  141.         if (result == 2)
  142.         {
  143.             graph.addEdge(player_two + shift_to_idx, player_one + shift_to_idx);
  144.             graph_reversed.addEdge(player_one + shift_to_idx, player_two + shift_to_idx);
  145.         }
  146.     }
  147. }
  148.  
  149. int get_count_comp(Graph graph_reversed, const std::vector<int>& t_out_array)
  150. {
  151.     int count_comp = 0;
  152.     for (int t_out : t_out_array)
  153.     {
  154.         if (graph_reversed.get_comp_num(t_out) == g_uninitialized)
  155.         {
  156.             graph_reversed.DFS_reversed(t_out, count_comp);
  157.             ++count_comp;
  158.         }
  159.     }
  160.  
  161.     return count_comp;
  162. }
  163.  
  164. int get_min_comp_size(
  165.     int num_people, const std::vector<comp_info>& comp_info_array, const int count_comp)
  166. {
  167.  
  168.     for (int i = 0; i < count_comp; ++i)
  169.     {
  170.         if (!comp_info_array[i].ishated && comp_info_array[i].comp_size < num_people)
  171.         {
  172.             num_people = comp_info_array[i].comp_size;
  173.         }
  174.     }
  175.  
  176.     return num_people;
  177. }
  178.  
  179. int main()
  180. {
  181.  
  182.     int num_people, count_games;
  183.     std::cin >> num_people >> count_games;
  184.  
  185.     Graph graph(num_people);
  186.     Graph graph_reversed(num_people);
  187.  
  188.     build_graphs(graph, graph_reversed, count_games);
  189.  
  190.     std::vector<int> t_out_array = graph.get_t_out_array();
  191.  
  192.     int count_comp = get_count_comp(graph_reversed, t_out_array);
  193.  
  194.     std::vector<comp_info> comp_info_array = graph_reversed.get_comp_info_array(num_people);
  195.  
  196.     int min_comp_size = get_min_comp_size(num_people, comp_info_array, count_comp);
  197.  
  198.     std::cout << num_people - min_comp_size + 1;
  199.  
  200.     return 0;
  201. }
  202.  
RAW Paste Data Copied