# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
720119 | vjudge1 | Bosses (BOI16_bosses) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
const int N=10001;
int n;
int ans=INT_MAX;
int sm;
int cnt;
vector<int>adj[N];
bool vis[N];
int dfs(int u,vector<int>adj2[]){
int sum=0;
for(int v:adj2[u]){
sum+=dfs(v,adj2);
}
sm+=sum+1;
return sum+1;
}
int main(){
ios_base::sync_with_stdio(0),cin.tie(0);
cin >> n;
for(int i=1; i<=n; i++){
int m;
cin >> m;
for(int j=1; j<=m; j++){
int v;
cin >> v;
adj[v].push_back(i);
}
}
for(int i=1; i<=n; i++){
cnt=0;
fiint(vis+1,vis+n+1,false);
vector<int>adj2[N];
queue<pair<int,int>>q;
q.push({0,i});
while(!q.empty()){
int u=q.front().second;
int p=q.front().first;
q.pop();
if(vis[u])continue;
vis[u]=true;
cnt++;
adj2[p].push_back(u);
for(int v:adj[u]){
if(!vis[v]){
q.push({u,v});
}
}
}
if(cnt<n)continue;
sm=0;
int x=dfs(i,adj2);
ans=min(ans,sm);
}
cout << ans;
return 0;
}