欧拉回路 （uoj117 欧拉回路模板题）
某天一名灵魂画师绘制了一幅图像。请找出欧拉回路，并解释其意义：在一个图中找到一个环，并确保每一条边仅在该环中出现一次。
一共两个子任务：
这张图是无向图。（50分）
这张图是有向图。（50分）
第一行一个整数 tt（tt∈{1, 2}），表示子任务的编号：当 tt=1 时，则标识该子任务处理无向图的情况；当 tt=2 时，则标识该子任务处理有向图的情况
第二行两个整数 n,mn,m，表示图的结点数和边数。
已知在接下来的 mm 行中存在若干条边的信息。每条边都包含两个整数 vi 和 ui（即顶点号），表示该条边（从 1 开始编号）。其中每个顶点号 vi 和 ui 都满足 1 ≤ vi, ui ≤ n
如果 t 等于 1，则表示节点 vivi 和 uiui 之间存在一条双向边。
如果 t 等于 2，则表示节点 vivi 和 uiui 之间存在一条单向边。
图中可能存在多重连接或自环节点。
输出格式
如果不可以一笔画，输出一行 “NO”。
否则，输出一行 “YES”，接下来一行输出一组方案。
假设 t 等于 1 ，则生成 m 个整数 p_1, p_2, \dots , p_m；设 e 等于 \lvert{p_i}\rvert（i = 1 到 m），其中每个 p_i 表示从 v_e 走到 u_e 的路径编号为正，则表示从 v_e 到 u_e；否则表示从 u_e 到 v_e. 类似地，在t = {2}的情况下也是如此.
样例一
input
1
3 3
1 2
2 3
1 3
output
YES
1 2 -3
样例二
input
2
5 6
2 3
2 5
3 4
1 2
4 2
5 1
output
YES
4 1 3 5 2 6
限制与约定
1≤n≤105,0≤m≤2×105
时间限制：1s
空间限制：256MB
思路
这是一个经典的欧拉回路问题，在这个问题中数据可能会导致常规算法难以及时处理。在DFS过程中将变量i的赋值改为引用操作能够显著提高算法效率（学到了这一优化技巧）。
代码实现
#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
typedef pair<ll,ll>P;
inline int read()
{
int x=0,t=1,c;
while(!isdigit(c=getchar())) if(c=='-') t=-1;
while(isdigit(c)) x=x*10+c-'0',c=getchar();
return x*t;
}
int to[N<<1],nxt[N<<1];
int t,n,m;
int head[N],cnt;
int indeg[N],outdeg[N];
bool vis[N<<1];
int ans[N<<1],tot;
inline void add(int u,int v)
{
to[++cnt]=v;
nxt[cnt]=head[u];
head[u]=cnt;
}
void dfs(int x)
{
for(int &i=head[x];i;i=nxt[i])
{
if(!vis[i])
{
int tmp=i;
vis[i]=true;
if(t==1)
{
if(i&1) vis[i+1]=true;
else vis[i-1]=true;
}
dfs(to[i]);
ans[++tot]=tmp;
}
}
}
int main()
{
t=read();n=read();m=read();
if(t==1)
{
for(register int i=0;i<m;++i)
{
int u,v;
u=read();v=read();
add(u,v);add(v,u);
indeg[u]++;indeg[v]++;
}
for(register int i=1;i<=n;++i)
{
if(indeg[i]&1)
{
puts("NO");
return 0;
}
}
}
else
{
for(register int i=0;i<m;++i)
{
int u,v;
u=read();v=read();
add(u,v);
outdeg[u]++;indeg[v]++;
}
for(register int i=1;i<=n;++i)
{
if(indeg[i]!=outdeg[i])
{
puts("NO");
return 0;
}
}
}
for(register int i=1;i<=n;++i)
{
if(head[i])
{
dfs(i);
break;
}
}
if(tot!=m)
{
puts("NO");
return 0;
}
puts("YES");
if(t==2)
{
for(register int i=0;i<tot;++i) printf("%d ",ans[tot-i]);
}
else
{
for(register int i=0;i<tot;++i)
{
if(ans[tot-i]&1) printf("%d ",(ans[tot-i]+1)/2);
else printf("%d ",ans[tot-i]/(-2));
}
}
return 0;
}
AI写代码