“蔚来杯“2022牛客暑期多校训练营1 J.Serval and Essay（启发式合并）

link

并收集假货 一直调不对

题意

给定一张n个点m条边的无环无重边的有向图，初始是每个点都是白色，你可以选择一个点染黑，紧接着对于每个点来说，若他的入边的起点都被染黑，他也就会变成黑色

做法

如果是他的话 入度为1 然后染色前面的点 之后，你可以把它们看成一个整体 但这个过程显然不能暴力 我们可以用队列模拟 一个启发式合并log优化 注意一下swap我们必须交换他的东西 "pre"集合
(我的代码跑得不快，卡在时限上)

#include  using namespace  std; //#define int long long typedef long long ll; typedef pair<int,int> pii; #define x first #define y second #define pb push_back #define inf 1e18 #define IOS std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define fer(i,a,b) for(int i=a;i<=b;i ) #define der(i,a,b) for(int i=a;i>=b;i--span class="token punctuation">)
const int maxn=1e5+10;
const int mod=1e9+7;
int qmi(int a,int b) { 
        
	int res=1;
	while(b) { 
        
		if(b&1) res=res*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return res;
}
const int N=2e5+10;
int dr[4][2]= { 
        { 
        -1,0},{ 
        1,0},{ 
        0,-1},{ 
        0,1}};
int n,k;
int fa[N];
set<int>g[N];  //pre
set<int>e[N];  //to
int _;
int sz[N];
int ttt;
int ans;
int cnt;
int find(int x) { 
        
	return fa[x]==x?:fa[x]=find(fa[x]);
}
void solve() { 
        
	cin>>n;
	fer(i,1,n)fa[i]=i, e[i].clear(),g[i].clear(),sz[i]=1;
	fer(i,1,n) { 
        
		int t;
		cin>>t;
		while(t--) { 
        
			int x;
			cin>>x;
			e[x].insert(i);
			g[i].insert(x);
		}
	}
	queue<pii>q;
	//fer(i,1,n)cout<
	fer(i,1,n)if(g[i].size()==1)q.push({ 
        i,*g[i].begin()});
// cout<
	while(!q.empty()) { 
        
		int p1=q.front().first;
		int p2=q.front().second;
		q.pop();
		int a=find(p1);
		int b=find(p2);
		if(a==b)continue;
		if(e[a].size()>e[b].size())swap(a,b),swap(g[a],g[b]);
		fa[a]=b;
		sz[b]+=sz[a];
		for(auto v:e[a]) { 
        
			int t=find(v);
			if(t==b)continue;
			e[b].insert(t);
			g[t].erase(a);
			g[t].insert(b);
			if(g[t].size()==1)q.push({ 
        t,b});
		}
	}
	ans=0;
	fer(i,1,n) { 
        
		// cout<
		ans=max(ans,sz[find(i)]);
	}
	cout << "Case #" <<++ ttt << ": " << ans << "\n";
}

int main() { 
        
	IOS;
	cin>>_;
	while(_--) solve();
	return 0;
}