Advertisement
Guest User

Untitled

a guest
Oct 21st, 2017
70
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.22 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <map>
  4. #include <list>
  5. #include <algorithm>
  6.  
  7. int main() {
  8.     int V;
  9.     std::cin >> V;
  10.     std::vector<std::vector<int>> adj_list;
  11.     std::vector<int> vertex_cover;
  12.     std::vector<int> vertex_degree;
  13.     for (int u = 0; u != V; ++u) {
  14.         int amount;
  15.         std::cin >> amount;
  16.         vertex_degree.push_back(amount);
  17.         std::vector<int> ver;
  18.         for (int i = 0; i != amount; ++i) {
  19.             int vertex;
  20.             std::cin >> vertex;
  21.             ver.push_back(vertex);
  22.         }
  23.         adj_list.push_back(ver);
  24.     }
  25.     for (size_t k = 0; k != V/2; ++k) {
  26.         for (size_t i = 0; i != V; ++i) {
  27.             if (vertex_degree[i] == 1) {
  28.                 int parent;
  29.                 for (auto elem : adj_list[i]) {
  30.                     if (vertex_degree[elem] != 0) {
  31.                         parent = elem;
  32.                     }
  33.                 }
  34.                 vertex_cover.push_back(parent);
  35.                 vertex_degree[parent] = 0;
  36.                 for (auto elem : adj_list[parent]) {
  37.                     vertex_degree[elem]--;
  38.                 }
  39.             }
  40.         }
  41.     }
  42.     std::cout << vertex_cover.size() << std::endl;
  43. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement