Untitled
#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