「启发式合并+Set」”蔚来杯”2022牛客暑期多校训练营1 J. Serval and Essay Solution

题目链接

题意：给定一个n个点m条边的有向图，保证没有重边和自环。初始所有点都是白色的，你可以选择一个点染黑，对于任意一个白色点来说，如果它的所有入度点都是黑色，那么它也可以被染为黑色，问染黑一个点后最多能有多少个点被染为黑色（包括初始点）。

首先对于一个入度为1的点，它是一定可以被它的“父亲”染色的。

这时可以将当前点的信息合并到它的“父亲”里面去。

信息包括当前点内包含的点的数量（经历了若干次合并后），和点所连出到其他点的连接信息。

为了保证复杂度，采用启发式合并。

总复杂度O(nlog^2n)，启发式合并一个log，set一个log。

#include <bits/stdc++.h>
using namespace std;
namespace IO{
    #define I inline
    I char tc(){static char tr[10000],*A=tr,*B=tr;return A==B&&(B=(A=tr)+fread(tr,1,10000,stdin),A==B)?EOF:*A++;}
    I void read(int &x){char c;for(;(c=tc())<48||c>57;);for(x=c-'0';(c=tc())>47&&c<58;x=(x<<1)+(x<<3)+c-'0');}
    //I void read(int &x){scanf("%d",&x);}
    #undef I
}using namespace IO;

const int N = 2e5+5, K = 5e5+5;
int T,n,k,Cnt,fa[N],sz[N];//fa即并查集维护集合信息，sz表示当前点内包含的点的数量。
set<int>F[N],gin[N];//F[x]表示x的前置条件，gin[x]表示x的连出信息。
int getf(int x){return x==fa[x]?x:fa[x]=getf(fa[x]);}

void Merge(int x,int y){
    x=getf(x),y=getf(y);
    if(x==y)return ;
    if(gin[x].size()<gin[y].size())swap(x,y);//启发式合并，小集合合并到大集合
    sz[x]+=sz[y];
    vector<int>P;
    for(auto i : gin[y]){
        gin[x].insert(i);//合并连出信息。
        F[i].erase(y),F[i].insert(x);//此时i点的前置条件由y点变为x点。
        if(F[i].size()==1)P.push_back(i);//如果在处理的过程中遇到了新的能合并的点，在当前点合并完成后继续合并新的点。
    }
    fa[y]=x;
    for(auto i : P)Merge(i,x);//用DFS栈代替BFS队列，也就是这题也可以用BFS来完成。
    return ;
}

int main()
{
    for(read(T);T;--T){
        ++Cnt;
        read(n);
        for(int i=1;i<=n;++i)fa[i]=i,sz[i]=1,F[i].clear(),gin[i].clear();
        for(int i=1;i<=n;++i){
            read(k);
            for(int j=1,x;j<=k;++j){
                read(x);
                F[i].insert(x);
                gin[x].insert(i);
            }
        }
        for(int i=1;i<=n;++i)if(F[i].size()==1){
            Merge(*F[i].cbegin(),i);
        }
        int Ans=0;
        for(int i=1;i<=n;++i)Ans=max(Ans,sz[i]);
        printf("Case #%d: %d\n",Cnt,Ans);
    }
}