题目描述

对一张无重边、无自环的 $n$ 个点的无向图，定义圈为可以重复经过同一个点多次、但不能多次经过同一条边的环。例如，$1\to 2\to 1$ 不是一个合法的圈，而 $1\to 2\to 3\to 4\to 5\to 3\to 1$ 是一个合法的圈。

定义无向图的双圈覆盖为：图的若干个圈，使得图中每条边恰好出现在两个圈中（无论方向）。

一个定理：如果一个图有哈密尔顿回路的话，它就一定有双圈覆盖。

现在给定一张无重边、无自环的 $n$ 个点的无向图，保证这个图存在哈密尔顿回路（会给出），且每个点的度数至少为 $3$。

求它的一个双圈覆盖。

题解

首先考虑如果每个点的度都是3的情况，可以发现只能是偶数个点，并且除去环上的边的话就是两两间有连边

于是我们加上环上一半且相间的边，不难发现这个图是个二分图，所以我们可以每条边都只走一遍就走完这张图，同理另一半也是一样，再加上走一个环，这样每条边就恰好经过了两边

现在考虑如果一个点的度大于3的话，可以考虑拆点，并且和原来编号的上一个拆的点相连接，这样我们就回到了度数都为3的情况了

具体的话可以画个图理解一下

代码

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int T,n,m,c,hd[N],V[N],W[N],pr[N],in[N],vis[N],nx[N],t=1,is[N],k;
vector<int>g[N],a[N];
void add(int u,int v,int w){nx[++t]=hd[u];V[hd[u]=t]=v;W[t]=w;
}
void ins(int u,int v,int w){add(u,v,w);add(v,u,w);
}
void bj(int u,int w){vis[u]=1;for (int i=hd[u];i;i=nx[i])if (W[i] && !vis[V[i]])is[i]=is[i^1]=w,bj(V[i],w^1);
}
void go(int u,int w){vis[u]=0;a[k].push_back(pr[u]);for (int i=hd[u];i;i=nx[i])if (W[i]==w){if (w && !is[i]) continue;if (!vis[V[i]]) continue;go(V[i],w^1);}
}
void work(){scanf("%d%d",&n,&m);c=n;for (int i=1;i<=n;i++)g[i].clear(),g[i].push_back(i),pr[i]=i,in[i]=0;for (int i=1,u,v;i<=m;i++){scanf("%d%d",&u,&v);if (u>v) swap(u,v);if (v==u+1 || (u==1 && v==n))continue;if (in[u]) g[u].push_back(++c),pr[c]=u,u=c;if (in[v]) g[v].push_back(++c),pr[c]=v,v=c;ins(u,v,0);in[u]=in[v]=1;}for (int i=1,v,z;i<=n;i++){v=i+1;if (v>n) v=1;z=g[i].size();ins(g[i][z-1],v,1);for (int j=0;j<z-1;j++)ins(g[i][j],g[i][j+1],1);}k=1;for (int i=1;i<=n;i++) a[k].push_back(i);bj(1,0);for (int i=1;i<=c;i++)if (vis[i]) k++,go(i,0);bj(1,1);for (int i=1;i<=c;i++)if (vis[i]) k++,go(i,0);printf("%d\n",k);for (int l,z,i=1;i<=k;i++){z=a[i].size();l=0;for (int j=1;j<z;j++)if (a[i][j]!=a[i][j-1])l++,a[i][l]=a[i][j];while(a[i][l]==a[i][0]) l--;printf("%d",l+1);for (int j=0;j<=l;j++)printf(" %d",a[i][j]);puts("");a[i].clear();}for (int i=1;i<=c;i++) hd[i]=0;t=1;
}
int main(){for (scanf("%d",&T);T--;work());return 0;
}