#include <bits/stdc++.h>
#define int long long
using namespace std;
int a;
vector<int> z[1000005];
int depth[1000005];
int min1=1e18;
int pre[1000005];
void bfs(int sta){
for (int i=1;i<=a;i++){
depth[i]=0;
pre[i]=1;
}
queue<int> q;
q.push(sta);
depth[sta]=1;
vector <pair<int,int>> v;
while (q.size()){
int pos=q.front();
q.pop();
for (auto p:z[pos]){
if (!depth[p]){
depth[p]=depth[pos]+1;
q.push(p);
v.push_back({p,pos});
}
}
}
int sum=0;
for (int i=1;i<=a;i++){
if (!depth[i]){
return;
}
}
while (v.size()){
auto [x,y]=v.back();
v.pop_back();
sum+=pre[x];
pre[y]+=pre[x];
}
sum+=pre[sta];
// cout << sta << " " << sum << "\n";
min1=min(min1,sum);
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> a;
for (int i=1;i<=a;i++){
int c;
cin >> c;
for (int j=1;j<=c;j++){
int x;
cin >> x;
z[x].push_back(i);
}
}
for (int i=1;i<=a;i++){
bfs(i);
}
cout << min1 << "\n";
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... |