"Weilai Cup" 2022 Niuke summer multi school training camp 1 J serval and essay (heuristic merger)

" Weilai cup "2022 Niuke summer multi school training camp 1 J Serval and Essay( Heuristic merging )

The question ： Given a acyclic and multiplicity free edge graph , All initial points are white , You can choose any point to make it black , The premise that other white dots can be polluted by black dots is All the edges are black dots . Ask the maximum number of black dots in the figure .

Ideas ： Consider merging sets , Heuristic merging . If $1$ Point dyeing black on No. 1 can make $2$ The number point turns black , $2$ Turning black on the number can make $3$ The number point turns black . Then we can directly choose to $1$ Dot dyeing ,$1、2、3$ Points are in a set . We just need to constantly merge the two sets ( Father gather and son gather ), If the only entry of the son's collection is the father's collection . take $size()$ Small sets merge into $size()$ In a large collection . The sum $O((n+m)lo{g}^{2}n)$ .

Code ：

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#pragma GCC optimize(3)
#define re register int
typedef pair<int,int>PII;
#define pb emplace_back
#define debug(a) cout<<a<<' ';
#define fer(i,a,b) for(re i=a;i<=b;i++)
#define der(i,a,b) for(re i=a;i>=b;i--)
int n;
const int N = 2e5+10;
set<int>in[N],out[N];
int p[N],si[N];
int cnt;
int find(int x){
    
    if(p[x]!=x)p[x]=find(p[x]);
    return p[x];
}
void merge(int u){
    
    int fa=*in[u].begin();
    u=find(u);
    fa=find(fa);
    if(u==fa)return ;
    if(out[u].size()>out[fa].size()){
    
        swap(u,fa);
    }
    si[fa]+=si[u];
    p[u]=fa;
    vector<int>vec;
    for(auto x:out[u]){
    
        out[fa].insert(x);
        in[x].erase(u);
        in[x].insert(fa);
        if(in[x].size()==1)vec.push_back(x);
    }
    for(auto x:vec)merge(x);
}
void cf(){
    
    cin>>n;
    for(int i=1;i<=n;i++)p[i]=i,si[i]=1;
    for(int i=1;i<=n;i++){
    
        int m;
        cin>>m;
        for(int j=1;j<=m;j++){
    
            int x;
            cin>>x;
            in[i].insert(x);
            out[x].insert(i);
        }
    }
    for(int i=1;i<=n;i++){
    
        if(in[i].size()==1){
    
            merge(i);
        }
    }
    int ma=0;
    for(int i=1;i<=n;i++){
    
        int x=p[i];
        ma=max(ma,si[x]);
    }
    for(int i=1;i<=n;i++){
    
        in[i].clear();
        out[i].clear();
    }
    cout<<"Case #"<<++cnt<<": "<<ma<<endl;
}
signed main(){
    
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int _=1;
    cin>>_;
    while(_--){
    
        cf();
    }
    return 0;
}