【XSY4182】下一个（next）（欧拉回路，构造）

题面

下一个（next）

题解

我们可以这么转化问题：给每一条边定向，使得每一个点的出度至少为 \(2\)。

证明新问题是原问题的充分条件：定好向后，我们先给每个点随便选一条出边，显然这些边形成若干连通块，且每个连通块点数不大于边数（都是基环树），且每个点都被恰好覆盖一次。然后我们把这些边删去，让剩下的边形成若干连通块，由新问题构造条件可知现在每个点肯定至少有一条出边被选上，于是能保证这些连通块中每个连通块点数不大于边数（都是基环树），且每个点都恰好又被恰好覆盖一次。

如何找呢，每个点度数至少为 \(4\) 是一个很关键的信息。我们先把原图建出来，并设置一个虚点 \(S\)，对于每一个点，如果它的度数为奇数，那么我们就将它和 \(S\) 连一条边。这样每个节点度数都是偶数（可以这么理解，一条边贡献两个度数所以总度数一定是偶数，而除了 \(S\) 以外的所有点的度数都是偶数了，所以 \(S\) 的度数也是偶数）。

然后我们跑欧拉回路，然后直接按欧拉回路的方向定向即可。原因：对于每个点 \(u\)，设 \(deg_u\) 为 \(u\) 在原图上的度数（没加虚边前的）。若 \(deg_u\) 为偶数，那么它的出度为 \(\frac{deg_u}{2}\geq 2\)，满足；若 \(deg_u\) 为奇数，那么我们新连了一条虚边，它的出度至少为 \(\frac{deg_u+1}{2}-1\geq 2\)，满足。

#include<bits/stdc++.h>

#define N 500010
#define M 1000010

using namespace std;

inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=(x<<1)+(x<<3)+(ch^'0');
		ch=getchar();
	}
	return x*f;
}

struct Edge
{
	int u,v;
};

struct data
{
	int v,id;
	data(){};
	data(int a,int b){v=a,id=b;}
};

const int E=(N+M)<<1;

int n,m,S;
int cnt=1,head[N],nxt[E],to[E];
bool vis[N],dir[E];
int deg[N];
int fa[N];
int tot,num[N];
int ans[M];

vector<data>e[N];

void adde(int u,int v)
{
	to[++cnt]=v;
	nxt[cnt]=head[u];
	head[u]=cnt; 
}

void dfs(int u)
{
	vis[u]=1;
	for(int &i=head[u];i;i=nxt[i])
	{
		if(dir[i]||dir[i^1]) continue;
		int v=to[i];
		dir[i]=1;
		dfs(v);
	}
}

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

void merge(int u,int v)
{
	int a=find(u),b=find(v);
	if(a!=b) fa[a]=b;
}

int main()
{
	n=read(),m=read();
	for(int i=1;i<=m;i++)
	{
		int u=read(),v=read();
		deg[u]++,deg[v]++;
		adde(u,v),adde(v,u);
	}
	S=n+1;
	for(int i=1;i<=n;i++)
		if(deg[i]&1) adde(i,S),adde(S,i);
	for(int i=1;i<=n;i++)
		if(!vis[i]) dfs(i);
	for(int i=2;i<=cnt;i++)
	{
		if(dir[i])
		{
			int u=to[i^1],v=to[i];
			if(u!=S&&v!=S) e[u].push_back(data(v,i/2));
		}
	}
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int u=1;u<=n;u++)
	{
		int v=e[u][0].v;
		merge(u,v);
	}
	for(int i=1;i<=n;i++)
		if(fa[i]==i) num[i]=++tot;
	for(int u=1;u<=n;u++)
		ans[e[u][0].id]=num[find(u)];
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int u=1;u<=n;u++)
		for(int i=1,size=e[u].size();i<size;i++)
			merge(u,e[u][i].v);
	for(int i=1;i<=n;i++)
		if(fa[i]==i) num[i]=++tot;
	for(int u=1;u<=n;u++)
		for(int i=1,size=e[u].size();i<size;i++)
			ans[e[u][i].id]=num[find(u)];
	printf("1\n%d\n",tot);
	for(int i=1;i<=m;i++)
		printf("%d ",ans[i]);
	return 0;
}
/*
5 10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5
*/