蒟蒻求助,第36个点T了┭┮﹏┭┮
查看原帖
蒟蒻求助,第36个点T了┭┮﹏┭┮
238408
vectorwyxSD省选加油楼主2020/8/27 23:59

RT,我查到半夜也没看出来我哪T了,恳请大佬指正QAQ

#include<iostream>
#include<cstdio>
#include<vector>
#define ll long long
#define fo(i,x,y) for(register int i=x;i<=y;++i)
#define go(i,x,y) for(register int i=x;i>=y;--i)
using namespace std;
inline int read(){ int x=0,fh=1; char ch=getchar(); while(!isdigit(ch)){ if(ch=='-') fh=-1; ch=getchar(); } while(isdigit(ch)){ x=(x<<1)+(x<<3)+ch-'0'; ch=getchar(); } return x*fh; }

const int maxn=1e5+5,maxm=1e6+5;
struct Edge{
	int to,next;
}e[maxm];
int head[maxn],tot,n,m,vis[maxm],degree[maxn],ji_dian[maxn],top1,st1[maxm],st2[maxm],top2,cnt;
void connect(int x,int y){
	e[++tot]=(Edge){y,head[x]};
	head[x]=tot;
}

void dfs(int now){
	for(int i=head[now];i;i=e[i].next){
		int p=e[i].to;
		if(!vis[i]) vis[i]=vis[((i-1)^1)+1]=1,dfs(p),++top2,st1[top2]=now,st2[top2]=p;
	}
}
int main(){
	n=read(),m=read();
	fo(i,1,m){
		int u=read(),v=read();
		degree[u]++,degree[v]++;		
		connect(u,v);
		connect(v,u);
	}
	fo(i,1,n)
		if(degree[i]&1) ji_dian[++top1]=i;
	for(int i=1;i<=top1;i+=2) connect(ji_dian[i],ji_dian[i+1]),connect(ji_dian[i+1],ji_dian[i]),++m;
	if(m&1) ++m,connect(1,1),connect(1,1);
	dfs(1);
	printf("%d\n",m);
	for(int i=1;i<=m;i+=2){
		printf("%d %d\n%d %d\n",st1[i],st2[i],st2[i+1],st1[i+1]);
	}
	return 0;
}
/*
4 6
1 2
2 3
3 4
4 1
1 3
1 3
-------------------------------------------------
6
1 2
3 4
1 4
3 2
1 3
1 3
*/
2020/8/27 23:59
加载中...