思路

只能按编号删除前缀，反向加点并查集合并，最大分量超过n/2时定位最小删除数。

参考程序（C++11）

#include <bits/stdc++.h>
using namespace std;
vector<int>p,sz;int findr(int x){return p[x]==x?x:p[x]=findr(p[x]);}int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int n;cin>>n;vector<vector<int>>g(n);for(int i=0;i<n;i++){int k;cin>>k;while(k--){int x;cin>>x;g[i].push_back(--x);g[x].push_back(i);}}p.resize(n);iota(p.begin(),p.end(),0);sz.assign(n,1);int maxsize=0;for(int i=n-1;i>=0;i--){maxsize=max(maxsize,1);for(int u:g[i])if(u>i){int a=findr(i),b=findr(u);if(a!=b){if(sz[a]<sz[b])swap(a,b);p[b]=a;sz[a]+=sz[b];maxsize=max(maxsize,sz[a]);}}if(maxsize>n/2){cout<<i+1<<'\n';return 0;}}}