萌新求助,为什么TLE#36
查看原帖
萌新求助,为什么TLE#36
195331
Mine_KingCattleya楼主2021/12/29 20:02

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
*/
2021/12/29 20:02
加载中...