Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- namespace
- {
- constexpr int g_uninitialized = -1;
- constexpr int shift_to_idx = -1;
- } // namespace
- struct vertex
- {
- std::vector<int> m_adj_list;
- bool m_isvisited = false;
- int m_comp_num = g_uninitialized;
- int m_t_out = g_uninitialized;
- };
- struct comp_info
- {
- bool m_ishated = false;
- int m_comp_size = 0;
- };
- class Graph
- {
- std::vector<vertex> m_graph;
- int m_size = 0;
- public:
- explicit Graph(const int size);
- void addEdge(const int i, const int j);
- void DFS(const int v_index, int& current_t_out);
- void DFS_reversed(const int v_index, const int current_comp_num);
- std::vector<int> get_t_out_array();
- std::vector<struct comp_info> get_comp_info_array(const int count_comp);
- int get_comp_num(const int v_index);
- };
- Graph::Graph(const int size)
- {
- this->m_graph.resize(size);
- this->m_size = size;
- }
- int Graph::get_comp_num(const int v_index)
- {
- return m_graph[v_index].m_comp_num;
- }
- void Graph::addEdge(const int i, const int j)
- {
- m_graph[i].m_adj_list.push_back(j);
- }
- void Graph::DFS(const int v_index, int& current_t_out)
- {
- if (!m_graph[v_index].m_isvisited)
- {
- m_graph[v_index].m_isvisited = true;
- for (int u_index : m_graph[v_index].m_adj_list)
- {
- DFS(u_index, current_t_out);
- }
- m_graph[v_index].m_t_out = current_t_out;
- ++current_t_out;
- }
- }
- void Graph::DFS_reversed(const int v_index, const int current_comp_num)
- {
- if (!m_graph[v_index].m_isvisited)
- {
- m_graph[v_index].m_isvisited = true;
- for (int u_index : m_graph[v_index].m_adj_list)
- {
- DFS_reversed(u_index, current_comp_num);
- }
- m_graph[v_index].m_comp_num = current_comp_num;
- }
- }
- std::vector<int> Graph::get_t_out_array()
- {
- for (int t_out = 0, v_index = 0; v_index < this->m_size; ++v_index)
- {
- DFS(v_index, t_out);
- };
- std::vector<int> t_out(this->m_size);
- for (int i = 0; i < this->m_size; ++i)
- {
- t_out[this->m_size - m_graph[i].m_t_out - 1] = i;
- }
- return t_out;
- }
- std::vector<struct comp_info> Graph::get_comp_info_array(const int count_comp)
- {
- std::vector<comp_info> comp_info_array(count_comp);
- for (int comp_num, i = 0; i < this->m_size; ++i)
- {
- comp_num = m_graph[i].m_comp_num;
- for (int u_index : m_graph[i].m_adj_list)
- {
- if (comp_num != m_graph[u_index].m_comp_num)
- {
- comp_info_array[comp_num].m_ishated = true;
- break;
- }
- }
- ++comp_info_array[comp_num].m_comp_size;
- }
- return comp_info_array;
- }
- void build_graphs(Graph& graph, Graph& graph_reversed, const int count_games)
- {
- for (int player_one, player_two, result, i = 0; i < count_games; ++i)
- {
- std::cin >> player_one >> player_two >> result;
- if (result == 1)
- {
- graph.addEdge(player_one + shift_to_idx, player_two + shift_to_idx);
- graph_reversed.addEdge(player_two + shift_to_idx, player_one + shift_to_idx);
- }
- if (result == 2)
- {
- graph.addEdge(player_two + shift_to_idx, player_one + shift_to_idx);
- graph_reversed.addEdge(player_one + shift_to_idx, player_two + shift_to_idx);
- }
- }
- }
- int get_count_comp(Graph& graph_reversed, const std::vector<int>& t_out_array)
- {
- int count_comp = 0;
- for (int t_out : t_out_array)
- {
- if (graph_reversed.get_comp_num(t_out) == g_uninitialized)
- {
- graph_reversed.DFS_reversed(t_out, count_comp);
- ++count_comp;
- }
- }
- return count_comp;
- }
- int get_min_comp_size(
- int num_people, const std::vector<comp_info>& comp_info_array, const int count_comp)
- {
- for (int i = 0; i < count_comp; ++i)
- {
- if (!comp_info_array[i].m_ishated && comp_info_array[i].m_comp_size < num_people)
- {
- num_people = comp_info_array[i].m_comp_size;
- }
- }
- return num_people;
- }
- int main()
- {
- int num_people, count_games;
- std::cin >> num_people >> count_games;
- Graph graph(num_people);
- Graph graph_reversed(num_people);
- build_graphs(graph, graph_reversed, count_games);
- std::vector<int> t_out_array = graph.get_t_out_array();
- int count_comp = get_count_comp(graph_reversed, t_out_array);
- std::vector<comp_info> comp_info_array = graph_reversed.get_comp_info_array(count_comp);
- int min_comp_size = get_min_comp_size(num_people, comp_info_array, count_comp);
- std::cout << num_people - min_comp_size + 1;
- return 0;
- }
Add Comment
Please, Sign In to add comment