题目传送门
题解
几乎是Fleury模板题。
一开始我们把图看作无向图,然后对于度为奇数的点增边,使得整个图的所有点都是偶数的。
代码
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;
const int N=1e5+5,M=3e5*4+5;
int fst[N],n,m,cnt=0,die[M],ans[M],totdo;
struct Edge{
int x,y,nxt,f,bh;
void set(int a,int b,int BH,int F){
x=a,y=b,bh=BH,f=F;
}
}e[M];
void read(int &x){
char ch=getchar();
x=0;
while (!('0'<=ch&&ch<='9'))
ch=getchar();
while ('0'<=ch&&ch<='9'){
x=x*10+ch-48;
ch=getchar();
}
}
void Make_Disedge(){
totdo=0;
int prev=0,in[N],m_=m;
memset(in,0,sizeof in);
for (int i=1;i<=cnt;i++)
in[e[i].y]++;
for (int i=1;i<=n;i++){
if (in[i]%2==0){
totdo++;
continue;
}
if (prev==0)
prev=i;
else {
e[++cnt].set(prev,i,++m_,0);
e[cnt].nxt=fst[prev],fst[prev]=cnt;
e[++cnt].set(i,prev,m_,1);
e[cnt].nxt=fst[i],fst[i]=cnt;
prev=0;
}
}
}
void Flenry(int rt){
for (int i=fst[rt];i;i=e[i].nxt){
if (die[e[i].bh]){
fst[rt]=e[i].nxt;
continue;
}
die[e[i].bh]=1;
ans[e[i].bh]=e[i].f;
fst[rt]=e[i].nxt;
Flenry(e[i].y);
break;
}
}
int main(){
scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++){
int a,b;
read(a),read(b);
e[++cnt].set(a,b,i,0);
e[cnt].nxt=fst[a],fst[a]=cnt;
e[++cnt].set(b,a,i,1);
e[cnt].nxt=fst[b],fst[b]=cnt;
}
Make_Disedge();
for (int i=1;i<=n;i++) Flenry(i);
printf("%d\n",totdo);
for (int i=1;i<=m;i++)
putchar(ans[i]+'0');
return 0;
}