SHARE
TWEET

Untitled

a guest Oct 21st, 2017 47 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <map>
  4.  
  5. int main() {
  6.     int V;
  7.     std::cin >> V;
  8.     std::map<int, std::vector<int>> adj_list;
  9.     std::vector<int> vertex_cover;
  10.     for (size_t u = 0; u != V; ++u) {
  11.         size_t amount;
  12.         std::cin >> amount;
  13.         for (size_t j = 0; j != amount; ++j) {
  14.             int vertex;
  15.             std::cin >> vertex;
  16.             adj_list[u].push_back(vertex);
  17.         }
  18.     }
  19.     for (size_t i = 0; i != V; ++i) {
  20.         if (adj_list[i].size() == 1) {
  21.             int parent = adj_list[i][0];
  22.             vertex_cover.push_back(parent);
  23.             std::cerr << parent << std::endl;
  24.             adj_list.erase(parent);
  25.             /*std::cerr << "====================" << std::endl;
  26.             for (auto elem : adj_list) {
  27.                 for (auto v : elem.second) {
  28.                     std::cerr << v << ' ';
  29.                 }
  30.                 std::cerr << std::endl;
  31.             }*/
  32.         }
  33.     }
  34.     std::cout << vertex_cover.size() << std::endl;
  35. }
RAW Paste Data
Top