欧拉回路-学习笔记
i207M
2019-07-11 21:21:43
~~重新学习欧拉回路~~
### 无向图
每个点的度数是偶数。
### 有向图
每个点的出度入度相等。
---
## 求法
从任意一个有边的点出发，沿着每条没有走过的边dfs，记录经过的边的**后序**历序，然后**reverse**一下就是欧拉回路的边序了。
记得要&i=head[x]，不然会退化为$O(m^2)$，这样就需要用一个临时变量记一下边的编号了。
```cpp
const int N=100005,M=200005*2;
int head[N],cnte,v[M],nx[M];
il void adde(int uu,int vv)
{
v[++cnte]=vv,nx[cnte]=head[uu],head[uu]=cnte;
}
int n,m;
bool vis[M];
int st[M],tp;
void dfs1(int x)
{
for(ri &i=head[x],t;i;i=nx[i])
{
if(vis[i>>1]) continue;
vis[i>>1]=1,t=i;
dfs1(v[i]);
st[++tp]=t;
}
}
void dfs2(int x)
{
for(ri &i=head[x],t;i;i=nx[i])
{
if(vis[i]) continue;
vis[i]=1,t=i;
dfs2(v[i]);
st[++tp]=t;
}
}
il void gun() {puts("NO"); exit(0);}
int ru[N],cu[N];
signed main()
{
#ifdef M207
freopen("in.in","r",stdin);
#endif
int typ; in(typ);
cnte=typ==1?1:0;
in(n),in(m);
for(ri i=1,a,b;i<=m;++i)
{
in(a),in(b);
adde(a,b);
++cu[a];
if(typ==1) adde(b,a),++cu[b];
else ++ru[b];
}
if(typ==1)
{
for(ri i=1;i<=n;++i)
if(cu[i]&1) gun();
}
else
{
for(ri i=1;i<=n;++i)
if(cu[i]!=ru[i]) gun();
}
for(ri i=1;i<=n;++i)
if(head[i])
{
if(typ==1) dfs1(i);
else dfs2(i);
break;
}
if(tp!=m) gun();
else
{
puts("YES");
reverse(st+1,st+1+tp);
if(typ==1)
{
for(ri i=1;i<=tp;++i)
out((st[i]>>1)*(st[i]&1?-1:1),' ');
}
else
{
for(ri i=1;i<=tp;++i) out(st[i],' ');
}
}
return 0;
}
```