Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <map>
- int main() {
- int V;
- std::cin >> V;
- std::map<int, std::vector<int>> adj_list;
- std::vector<int> vertex_cover;
- for (size_t u = 0; u != V; ++u) {
- size_t amount;
- std::cin >> amount;
- for (size_t j = 0; j != amount; ++j) {
- int vertex;
- std::cin >> vertex;
- adj_list[u].push_back(vertex);
- }
- }
- for (size_t i = 0; i != V; ++i) {
- if (adj_list[i].size() == 1) {
- int parent = adj_list[i][0];
- vertex_cover.push_back(parent);
- std::cerr << parent << std::endl;
- adj_list.erase(parent);
- /*std::cerr << "====================" << std::endl;
- for (auto elem : adj_list) {
- for (auto v : elem.second) {
- std::cerr << v << ' ';
- }
- std::cerr << std::endl;
- }*/
- }
- }
- std::cout << vertex_cover.size() << std::endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement