Submission #392760

#TimeUsernameProblemLanguageResultExecution timeMemory
392760IwanttobreakfreeBosses (BOI16_bosses)C++17
0 / 100
1 ms204 KiB
#include <iostream>
#include <vector>
#include <set>
using namespace std;
bool bos;
void dfs(int a,int ori,vector<bool>& visto,vector<set<int> >& v,vector<long long int>& acumulacion,int parent){
    bos=false;
    visto[a]=true;
    for(int x: v[a]){
        if(!visto[x]){
            bos=true;
            dfs(x,ori,visto,v,acumulacion,a);
        }
    }
    acumulacion[parent]+=acumulacion[a];
    //cout<<acumulacion[a]<<' '<<a<<'\n';
    if(a==ori)return;
}
int main(){
  cin.tie(0);
  cout.tie(0);
  ios::sync_with_stdio(false);
    long long int n,k,mini=1e18,a;
    cin>>n;
    vector<set<int> >v (n,set<int>());
    vector<long long int> acumulacion;
    vector<bool>visto;
    for(int i=0;i<n;i++){
        cin>>k;
        while(k--){
            cin>>a;
            a--;
            v[a].insert(i);
        }
    }
    for(int i=0;i<n;i++){
    visto=vector<bool>(n,false);
    acumulacion=vector<long long int>(n,1);
    dfs(i,i,visto,v,acumulacion,i);
    //cout<<acumulacion[i]<<' ';
    if(mini>acumulacion[i])mini=acumulacion[i];
}
    cout<<mini;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...