Untitled

 avatar
unknown
c_cpp
a month ago
927 B
2
Indexable
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

vector<int> g[200005];
int dp[200005][2];
void dfs(int node, int par) {
    dp[node][0] = 0, dp[node][1] = 1;
    for (auto x : g[node])
        if (x != par) {
            dfs(x, node);
            dp[node][0] += dp[x][1];
            dp[node][1] += min(dp[x][1], dp[x][0]);
        }
}

int32_t main() {
    while (1) {
        int n; cin >> n;
        if (!n) return 0;
        for (int i = 1; i <= n; ++i) {
            int t; cin >> t;
            while (t--) {
                int v; cin >> v;
                g[i].push_back(v);
            }
        }

        if (n == 1) cout << 1 << endl;
        else {
            memset(dp, -1, sizeof(dp));
            dfs(1, 0);
            cout << min(dp[1][0], dp[1][1]) << endl;
        }
        for (int i = 1; i <= n; ++i)
            g[i].clear();
    }
}
Leave a Comment