#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long;
using ll = long long;
#define x first
#define y second
vector<vector<int>> adj;
ll bdfs(int f,int n){
vector<vector<int>> ch(n+1);
vector<bool> visit(n+1,false);
int used=0;
queue<int> q;
q.push(f);
visit[f]=true;
used++;
int v;
while(!q.empty()){
v=q.front();
q.pop();
for(int c:adj[v]){
if(!visit[c]){
visit[c]=true;
ch[v].push_back(c);
used++;
q.push(c);
}
}
}
if(used<n){
return LLONG_MAX;
}
vector<int> dp(n+1,0);
ll sum=0;
stack<tuple<int,int,bool>> s;
s.push({f,-1,0});
visit[f]=true;
while(!s.empty()){
auto [v,p,st]=s.top();
s.pop();
if(st==0){
s.push({v,p,1});
for(int c:ch[v]){
if(c==p) continue;
s.push({c,v,0});
}
}
else{
dp[v]=1;
for(int c:ch[v]){
if(c!=p){
dp[v]+=dp[c];
}
}
sum+=dp[v];
}
}
return sum;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int n;cin >> n;
adj.resize(n+1);
for(int i=1,k;i<=n;i++){
cin >> k;
for(int j=0,v;j<k;j++){
cin >> v;
adj[v].push_back(i);
}
}
ll sum=LLONG_MAX;
for(int i=1;i<=n;i++){
if(adj[i].size()>1) sum=min(sum,bdfs(i,n));
}
if(sum==LLONG_MAX){
for(int i=1;i<=n;i++){
if(adj[i].size()>0) sum=min(sum,bdfs(i,n));
}
}
cout << sum;
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... |