Untitled
unknown
c_cpp
10 months ago
927 B
4
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();
}
}Editor is loading...
Leave a Comment