Advertisement
Guest User

Untitled

a guest
Oct 15th, 2019
91
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.69 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. struct node {
  5.     int v;
  6.     int cover = 0;
  7.     std::vector<node*> neighbours;
  8. };
  9.  
  10. node* make_tree(int x, std::vector<bool> &used, const std::vector<std::vector<int>> &g) {
  11.     used[x] = true;
  12.  
  13.     node *tree = new node();
  14.     tree->v = x;
  15.     for (int i = 0; i < g[x].size(); ++i) {
  16.         if (!used[g[x][i]]) {
  17.             tree->neighbours.push_back(make_tree(g[x][i], used, g));
  18.         }
  19.     }
  20.  
  21.     return tree;
  22. }
  23.  
  24. int cover_func(node *root) {
  25.     if (root->neighbours.empty())
  26.         return 0;
  27.     if (root->cover != 0)
  28.         return root->cover;
  29.  
  30.     int if_include = 1;
  31.     for (int i = 0; i < root->neighbours.size(); ++i) {
  32.         if_include += cover_func(root->neighbours[i]);
  33.     }
  34.  
  35.     int if_except = 0;
  36.     for (int i = 0; i < root->neighbours.size(); ++i) {
  37.         ++if_except;
  38.         for (int j = 0; j < root->neighbours[i]->neighbours.size(); ++j) {
  39.             if_except += cover_func(root->neighbours[i]->neighbours[j]);
  40.         }
  41.     }
  42.  
  43.     if (if_include < if_except) {
  44.         root->cover = if_include;
  45.     } else {
  46.         root->cover = if_except;
  47.     }
  48.  
  49.     return root->cover;
  50. }
  51.  
  52. int main() {
  53.     int n;
  54.     std::cin >> n;
  55.     std::vector<std::vector<int>> graph(n);
  56.     for (int i = 0; i < n; ++i) {
  57.         int num, tmp;
  58.         std::cin >> num;
  59.         for (int j = 0; j < num; ++j) {
  60.             std::cin >> tmp;
  61.             graph[i].push_back(tmp);
  62.         }
  63.     }
  64.  
  65.     std::vector<bool> used(n, false);
  66.     int ans = 0;
  67.     for (int i = 0; i < n; ++i) {
  68.         if (!used[i]) {
  69.             ans += cover_func(make_tree(i, used, graph));
  70.         }
  71.     }
  72.  
  73.     std::cout << ans << "\n";
  74. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement