求问TLE on 36 删边寄了?
查看原帖
求问TLE on 36 删边寄了?
85977
SSpider_Man楼主2024/5/30 21:42
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,M=1e6+5;
int n,m,deg[N],p,head[N],to[M],vis[M],nxt[M],tot=1;
void add(int u,int v){
	tot++;
	to[tot]=v;
	nxt[tot]=head[u];
	head[u]=tot;
}
void dfs(int u){
//	cout<<u<<" "<<head[u]<<"\n";
	for(int i=head[u];i;i=nxt[i]){
		head[u]=nxt[i];
		if(vis[i]) continue;
		vis[i]=vis[i^1]=1;
		int v=to[i];
		dfs(v);
		tot++;
		if(tot&1) printf("%d %d\n",u,v);
		else printf("%d %d\n",v,u);
	}
}
int main(){
	
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		add(u,v);
		add(v,u);
		deg[u]++;
		deg[v]++;
	}
	for(int i=1;i<=n;i++){
		if(!(deg[i]&1)) continue;
		if(!p) p=i;
		else{
			add(i,p);
			add(p,i);
			m++;
			p=0;
		}
	}
	if(m&1) m++,add(1,1);
	printf("%d\n",m);
	tot=0;
	dfs(1);
	return 0;
}
2024/5/30 21:42
加载中...