#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vii = vector<vi>;
int n;
int ans(int root, vii & adj) {
vector<bool> used(n+1);
vector<ll> dp(n+1);
vector<int> par(n+1);
stack<int> order;
queue<int> q;
q.push(root);
used[root] = true;
int vis = 0;
while(!q.empty()) {
int v = q.front();
q.pop();
used[v] = true;
vis++;
order.push(v);
for(auto cld : adj[v]) {
if(!used[cld]) {
q.push(cld);
used[cld] = true;
par[cld] = v;
}
}
}
ll res = 0;
if(vis != n) return INT32_MAX;
// detect leaves
while(!order.empty()) {
int fr = order.top();
order.pop();
for(auto cld : adj[fr]) {
if(par[cld] == fr) {
dp[fr] += dp[cld];
}
}
dp[fr]++;
res += dp[fr];
}
return res;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n;
vii adj(n+1);
for(int i = 1; i <= n;i++) {
int k; cin >> k;
for(int j = 0; j < k; j++) {
int a; cin >> a;
adj[a].push_back(i);
}
}
int res = INT32_MAX;
for(int i = 1; i <= n;i++) {
res = min(res,ans(i,adj));
}
cout << res;
return 0;
}
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |