自动搬运

查看原文

来自洛谷，原作者为

	EXODUS I love you this much

搬运于2025-08-24 22:28:38，当前版本为作者最后更新于2022-10-11 20:28:54，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Part 1：前言

神仙构造题。

下文中，我们用小写代替原文中的大写，用 $col_i$ 代表原文的 $c_i$。

Part 2：正文

首先可以猜测到最小的颜色数为度数最大的点的度数，不会证也没关系，有一点是显然的，就是最终答案 $c$ 不小于度数最大的点的度数 $d_max$。

注意到题目给了一个非常奇怪的范围：$x$ 为不小于 $c$ 的最小的 $2$ 的正整数次幂。换言之，$x=2^{\left\lceil{\log_2 c}\right\rceil}\ge2^{\left\lceil{\log_2 d_{max}}\right\rceil}$，对于这种范围，一般可以想到是分治构造了。

考虑对边集进行划分，每次我们都试图将原来的边集划分为两个边集，每个边集中度数最大的点都是原来边集中最大的点的度数的一半。当我们把边集划分后点的度数最大是 $1$ 时，就把这个边集内所有的边染成同色的。这样做最多会分治 $\left\lceil{\log_2 d_{max}}\right\rceil$ 轮，每轮合并答案都会让颜色种类数乘 $2$，答案不会超过 $2^{\left\lceil{\log_2 d_{max}}\right\rceil}$。

接下来考虑如何划分。我们新建两个虚点 $x',y'$ 分属于二分图两侧。把一侧度数为奇数的点向另一侧的虚点连边，这样每个点的度数都是偶数，一定存在一条欧拉回路。我们将欧拉回路上的边交替染色，同色的边属于一个边集，这样就能使得每个点点度数大小减半（感性理解，对于每个点，出现在欧拉回路中度数除二上取整次，每次涉及到两条边且被染成不同颜色）。

时间复杂度 $O(n\log n)$（这里视 $n,m$ 同阶）。

Part 3：代码

#define u first
#define v second
#define pb push_back
const int N=2e5+7,M=1e6+7;
int l,r,m,n;
vector<np>e,ne;
vector<int>to[N];
int tim[N],deg[N],_clock=0;
int col[M];
int vis[M];

void reset(int x,vector<int>&V){
	tim[x]=_clock;
	to[x].clear();
	deg[x]=0;V.pb(x);
}

int c=0;

void dfs(int u){
	for(;!to[u].empty();){
		int id=to[u].back();
		to[u].pop_back();
		if(vis[id]==_clock)continue;
		
		col[id]=(c^=1);
		vis[id]=_clock;
		dfs(ne[id].u+ne[id].v-u);
	}
}

vector<int>solve(vector<np>E){
	if(!E.size())return {};
	++_clock;
	ne=E;
	vector<int>V;
	bool flag=0;
	int siz=E.size(),nsiz=ne.size();
	for(int i=0;i<siz;i++){
		np edge=E[i];
		int u=edge.u,v=edge.v;
		if(tim[u]!=_clock)reset(u,V);
		if(tim[v]!=_clock)reset(v,V);
		deg[u]++,deg[v]++;
		if(deg[u]>1||deg[v]>1)flag=1;
		to[u].pb(i),to[v].pb(i);
	}
	if(!flag){
		vector<int>res(E.size(),1);
		return res;
	}
	deg[n+1]=0;
	for(int i:V){
		if(deg[i]&1){
			if(i<=l||i==n+1){
				deg[n+2]++,deg[i]++;
				to[n+2].pb(nsiz),to[i].pb(nsiz),ne.pb({i,n+2});
				nsiz++;
			}else{
				deg[n+1]++,deg[i]++;
				to[n+1].pb(nsiz),to[i].pb(nsiz),ne.pb({i,n+1});
				nsiz++;
			}
		}
	}
	if(deg[n+1]&1){
		deg[n+2]++,deg[n+1]++;
		to[n+2].pb(nsiz),to[n+1].pb(nsiz),ne.pb({n+1,n+2});
		nsiz++;
	}
	for(int i:V){dfs(i);}
	vector<np>el,er;
	vector<int>cl;
	for(int i=0;i<siz;i++){
		if(col[i])er.pb(E[i]);
		else el.pb(E[i]);
		cl.pb(col[i]);
	}
	vector<int>rl=solve(el);
	vector<int>rr=solve(er);
	int ansl=0;
	for(int i:rl)ansl=max(ansl,i);
	vector<int>res;
	int tmpl=0,tmpr=0;
	for(int i=0;i<siz;i++){
		if(cl[i])res.pb(ansl+rr[tmpr++]);
		else res.pb(rl[tmpl++]);
	}
	return res;
}

int main(){
	l=read(),r=read(),m=read();n=l+r;
	for(int i=1;i<=m;i++){
		int u=read(),v=read();
		e.pb(mp(u,v+l)); 
	}
	vector<int>ans=solve(e);
	int res=0;
	for(int i:ans)res=max(res,i);
	cout<<res<<endl;
	for(int i:ans)printf("%d\n",i);
	return 0;
}