题意：给一张 \(n\) 个点 \(m\) 条边的简单连通无向图，保证 \(m\) 为偶数。可知度数为奇数的点共有偶数个，你需要将它们两两分组，对于每一组点 \(u,v\)，你要找到一条包含偶数条边的 \(u\) 和 \(v\) 之间的不重边路径，同时你要保证一条边至多在一条路径中出现。请求出任意一组构造方案。
\(n,m\leq 10^6\)。
题解：
为了保证路径长度是偶数，我们考虑这么一种做法：
-
将原图 \(G\) 中的边两两匹配，满足匹配的两条边恰有一个公共端点，且一条边恰在一个匹配中。
匹配的方案可以用 dfs 树从下往上递推得到：从下往上枚举每个点，优先将非父亲边的还未匹配的出边两两匹配，若还剩一条边不能匹配，则与父亲边匹配即可。由于 \(m\) 为偶数，所以最后一定有解。
我们建立一个新图 \(G'\)：对于一组匹配 \((u,v),(v,w)\)，我们在新图中连边 \((u,w)\)。
发现任意一个点 \(u\) 在 \(G\) 中的度数奇偶性和 \(u\) 在 \(G'\) 中的度数奇偶性相同。
-
我们补全 \(G'\)：新建一个虚点向所有 \(G'\) 中度数为奇数的点连边，使得 \(G'\) 存在欧拉回路。
然后直接跑欧拉回路，每一轮进出虚点即对应着 \(G'\) 中一条从奇点到奇点的路径，即 \(G\) 中一条从奇点到奇点且长度为偶数的路径。
时间复杂度 \(O(n+m)\)。
#include<bits/stdc++.h>
#define N 250010
#define fi first
#define se second
#define pii pair<int,int>
#define mk(a,b) make_pair(a,b)
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;
}
int n,m;
namespace G2
{
bool deg[N],vise[(N*3)>>1];
int cnt=1,head[N],nxt[N*3],to[N*3];
pii eid[N*3];
vector<int> path;
void adde(int u,int v,pii e)
{
deg[u]^=1;
to[++cnt]=v;
eid[cnt]=e;
nxt[cnt]=head[u];
head[u]=cnt;
}
void euler(int u)
{
for(int &i=head[u];i;i=nxt[i])
{
if(vise[i>>1]) continue;
vise[i>>1]=1;
path.push_back(i);
euler(to[i]);
}
}
void main()
{
int tot=0;
for(int i=1;i<=n;i++)
if(deg[i]) adde(i,n+1,mk(114,514)),adde(n+1,i,mk(1919,810)),tot++;
euler(n+1);
tot>>=1;
int ed=-1;
while(tot--)
{
int st=++ed;
while(to[path[ed]]!=n+1) ed++,assert(ed<(int)path.size());
printf("%d %d %d\n",to[path[st]],to[path[ed-1]],(ed-1-st)<<1);
for(int i=st+1;i<ed;i++)
printf("%d %d ",eid[path[i]].fi,eid[path[i]].se);
puts("");
}
}
}
namespace G1
{
int cnt=1,head[N],nxt[N<<1],to[N<<1];
bool vis[N],match[N];
void adde(int u,int v)
{
to[++cnt]=v;
nxt[cnt]=head[u];
head[u]=cnt;
}
void dfs(int u,int from)
{
vis[u]=1;
int lstp=0,lste;
for(int i=head[u];i;i=nxt[i])
{
if(!(i^from^1)) continue;
int v=to[i];
if(!vis[v]) dfs(v,i);
if(!match[i>>1])
{
if(!lstp) lstp=v,lste=i>>1;
else
{
match[lste]=match[i>>1]=1;
G2::adde(lstp,v,mk(lste,i>>1));
G2::adde(v,lstp,mk(i>>1,lste));
lstp=0;
}
}
}
if(lstp)
{
int fa=to[from^1];
match[lste]=match[from>>1]=1;
G2::adde(lstp,fa,mk(lste,from>>1));
G2::adde(fa,lstp,mk(from>>1,lste));
}
}
void main(){dfs(1,0);}
}
int main()
{
// freopen("2asy30.in","r",stdin);
// freopen("2asy30_my.out","w",stdout);
n=read(),m=read();
for(int i=1;i<=m;i++)
{
int u=read(),v=read();
G1::adde(u,v),G1::adde(v,u);
}
G1::main();
G2::main();
return 0;
}