#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<ll, ll>
#define fi first
#define sec second
#define ld long double
const int MAXN = 5e3;
const ll INF = 1e18;
const int MOD = 998244353;
const ld eps = 1e-6;
vector<ll> boss[MAXN + 5];
ll dist[MAXN + 5], vis[MAXN + 5];
vector<ll> adj[MAXN + 5];
ll sum = 0;
void dfs(ll idx){
dist[idx] = 1;
for(auto i : adj[idx]){
dfs(i);
dist[idx] += dist[i];
}
sum += dist[idx];
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int tc = 1;
// cin >> tc;
for(;tc--;){
ll N; cin >> N;
for(int i = 1; i <= N; i++){
ll K; cin >> K;
for(int j = 1; j <= K; j++){
ll x; cin >> x;
boss[x].push_back(i);
}
}
ll ans = INF;
for(int i = 1; i <= N; i++){
for(int j = 1; j <= N; j++){
adj[j].clear();
dist[j] = INF;
vis[j] = 0;
}
queue<ll> q;
vis[i] = 1;
q.push(i);
ll cur = 0;
for(;!q.empty();){
auto x = q.front(); q.pop();
cur++;
for(auto nxt : boss[x]){
if(!vis[nxt]){
vis[nxt] = 1;
adj[x].push_back(nxt);
q.push(nxt);
}
}
}
if(cur != N) continue;
sum = 0;
dfs(i);
ans = min(ans, sum);
}
cout << ans << "\n";
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |