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