Advertisement
Guest User

Untitled

a guest
Oct 21st, 2017
90
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.02 KB | None | 0 0
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement