2022牛客多校第一场J（启发式合并）

题意

Serval要完成一篇英文论文，论文中有n个论点。一个论点的正确性依赖这个论点的前置，如果一个论点的前置论点都是正确的，那么这个论点就是正确的。初始情况下，所有论点都无法被证明是正确的，Serval可以从n个论点中选择一个论点作为论据基础，认为这个论点是正确的，求正确论点数量的最大值。

对题目进行抽象：给定一张n个点m条边的有向无环图，初始时可以选择一个点染黑，其余点均为白点，若某个点所有入边的起点均为黑点，则该点可以被染黑，最大化图中黑点数量。

分析

以下面这张图为例，如果将1号点染黑，由于2号点入度为1且入边的起点被染为黑色，则2也可以被染黑。1和2都被染黑后，可以将1和2视为同一个点，即进行缩点。继续进行染色，发现3号点入度为1且入边的起点已染为黑色，3号点可染黑并将1、2、3缩点，同理4、5也可染黑，最终5个点被缩为1个点。模拟上述过程发现，每次要寻找缩点后入度为1的点并将其加入黑色点的集合中。从上述过程可以发现合并的次数是有限的，考虑用启发式合并加速迭代过程，两个集合合并时，点数少的集合向点数多的集合合并，每个点最多被合并$log(n)log(n)$次，用set维护每个集合，时间复杂度$O((n+m)lo{g}^{2}n)O((n+m)log^\{2\}n)$。

AC代码

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const int N=2e5+10;
set<int> in[N],out[N];
int pa[N],sz[N];

int find(int x)
{
	return pa[x]==x?pa[x]:pa[x]=find(pa[x]);
}

void merge(int x,int y)
{
	x=find(x),y=find(y);
	if(x==y) return ;
	if(out[x].size()<out[y].size()) swap(x,y);
	pa[y]=x;
	sz[x]+=sz[y];
	vector<pair<int,int>> vec;
	for(auto z:out[y])
	{
		out[x].insert(z);
		in[z].erase(y);
		in[z].insert(x);
		if(in[z].size()==1)
		{
			vec.push_back({z,x});
		}
	}
	for(auto it:vec) merge(it.first,it.second);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int T;
	cin>>T;
	for(int _=1;_<=T;_++)
	{
		int n;
		cin>>n;
		for(int i=1;i<=n;i++) pa[i]=i,sz[i]=1;
		for(int i=1;i<=n;i++)
		{
			int k;
			cin>>k;
			for(int j=1;j<=k;j++)
			{
				int y;
				cin>>y;
				in[i].insert(y);
				out[y].insert(i);
			}
		}
		for(int i=1;i<=n;i++)
		{
			if(in[i].size()==1)
			{
				merge(*in[i].begin(),i);
			}
		}
		int ans=0;
		for(int i=1;i<=n;i++) ans=max(ans,sz[i]);
		for(int i=1;i<=n;i++) in[i].clear(),out[i].clear();
		cout<<"Case #"<<_<<": "<<ans<<endl;
	}
	
	return 0;
}