제출 #218613

#제출 시각아이디문제언어결과실행 시간메모리
218613nicolaalexandraBosses (BOI16_bosses)C++14
0 / 100
5 ms640 KiB
/// macar elimin ideile proaste
#include <bits/stdc++.h>
#define DIM 5010
#define INF 2000000000
using namespace std;
vector <int> v[DIM],L[DIM];
int f[DIM],s[DIM],viz[DIM];
deque <int> c;
int n,i,j,nr,x;
void dfs (int nod, int tata){
    s[nod] = viz[nod] = 1;
    for (auto vecin : L[nod])
        if (vecin != tata){
            dfs (vecin,nod);
            s[nod] += s[vecin];
        }
}
int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n;
    for (i=1;i<=n;i++){
        cin>>nr;
        for (j=1;j<=nr;j++){
            cin>>x;
            v[x].push_back(i);
        }
    }
    int sol = INF;
    for (i=1;i<=n;i++){ /// radacina
        c.clear();
        memset (f,0,sizeof f);
        memset (s,0,sizeof s);
        memset (viz,0,sizeof viz);

        for (j=1;j<=n;j++)
            L[j].clear();


        c.push_back(i);
        f[i] = 1;

        while (!c.empty()){
            int nod = c.front();
            c.pop_front();
            for (auto vecin : v[nod]){
                if (!f[vecin]){
                    L[nod].push_back(vecin);
                    L[vecin].push_back(nod);

                    f[vecin] = 1;
                    c.push_back(vecin);
                }}}

        /*for (j=1;j<=n;j++)
            if (!viz[j])
                dfs (j,0);*/
        dfs (i,0);

        int sum = 0;
        for (j=1;j<=n;j++){
            sum += s[j];
            if (!s[j])
                sum++;
        }
        sol = min (sol,sum);
    }
    cout<<sol;




    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...