Rt。边也删了,为啥还是TLE,求大佬帮忙康康
难道我删边写挂了?
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,m,du[100005],vis[800005],cnt;
struct graph
{
int tot;
int hd[100005];
int nxt[800005],to[800005];
graph(){tot=1;return ;}
void add(int u,int v)
{
nxt[++tot]=hd[u];
hd[u]=tot;
to[tot]=v;
return ;
}
}g;
void dfs(int now)
{
for(int i=g.hd[now],lst=0;i;i=g.nxt[i])
{
if(i==g.hd[now]) g.hd[now]=g.nxt[i];
else g.nxt[lst]=g.nxt[i];
if(vis[i]==1) continue;
vis[i]=vis[i^1]=1;
dfs(g.to[i]);
if((++cnt)&1) printf("%d %d\n",now,g.to[i]);
else printf("%d %d\n",g.to[i],now);
}
return ;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int u,v;
scanf("%d%d",&u,&v);
g.add(u,v);
g.add(v,u);
du[u]++,du[v]++;
}
int one=0;
for(int i=1;i<=n;i++)
if(du[i]%2)
{
if(one==0) one=i;
else g.add(one,i),g.add(i,one),m++,one=0;
}
if(m%2) g.add(1,1),g.add(1,1),m++;
printf("%d\n",m);
dfs(1);
return 0;
}
/*
3 4
1 1
2 2
3 2
2 1
*/