Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- struct node {
- int v;
- int cover = 0;
- std::vector<node*> neighbours;
- };
- node* make_tree(int x, std::vector<bool> &used, const std::vector<std::vector<int>> &g) {
- used[x] = true;
- node *tree = new node();
- tree->v = x;
- for (int i = 0; i < g[x].size(); ++i) {
- if (!used[g[x][i]]) {
- tree->neighbours.push_back(make_tree(g[x][i], used, g));
- }
- }
- return tree;
- }
- int cover_func(node *root) {
- if (root->neighbours.empty())
- return 0;
- if (root->cover != 0)
- return root->cover;
- int if_include = 1;
- for (int i = 0; i < root->neighbours.size(); ++i) {
- if_include += cover_func(root->neighbours[i]);
- }
- int if_except = 0;
- for (int i = 0; i < root->neighbours.size(); ++i) {
- ++if_except;
- for (int j = 0; j < root->neighbours[i]->neighbours.size(); ++j) {
- if_except += cover_func(root->neighbours[i]->neighbours[j]);
- }
- }
- if (if_include < if_except) {
- root->cover = if_include;
- } else {
- root->cover = if_except;
- }
- return root->cover;
- }
- int main() {
- int n;
- std::cin >> n;
- std::vector<std::vector<int>> graph(n);
- for (int i = 0; i < n; ++i) {
- int num, tmp;
- std::cin >> num;
- for (int j = 0; j < num; ++j) {
- std::cin >> tmp;
- graph[i].push_back(tmp);
- }
- }
- std::vector<bool> used(n, false);
- int ans = 0;
- for (int i = 0; i < n; ++i) {
- if (!used[i]) {
- ans += cover_func(make_tree(i, used, graph));
- }
- }
- std::cout << ans << "\n";
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement