欧拉回路
- 在一个图中，一条路径能将所有边都走且仅走一遍的路径，为欧拉路径
- 欧拉回路是特殊的欧拉路径，即起点等于终点
存在欧拉路径和欧拉回路的条件
- 在无向图中，所有点连通
- 存在欧拉路径：度数为奇数的点有0个或2个
- 存在欧拉回路：度数为奇数的点有0个
- 在有向图中，所有点连通
- 存在欧拉路径：要么所有点出度等于入度；要么除了两个点出度等于入度 剩余两个点：一个点出度比入度多1(起点)，一个点入度比出度多1(终点)
- 存在欧拉回路：所有点出度等于入度
cpp
int e[M],ne[M],h[N],idx;
int din[N],dout[N];
bool used[M];
int n,m,ans[M],cnt,type;
void add(int a,int b){
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dfs(int u){
for(int i=h[u];~i;i=h[u]){
if(used[i]){
h[u]=ne[i];
continue;
}
used[i]=1;
if(type==1)used[i^1]=1;
h[u]=ne[i];
dfs(e[i]);
int t;
if(type==1){
t=i/2+1;
if(i&1)t=-t;
}
else t=i+1;
ans[++cnt]=t;
}
}
void solve(){
cin>>type>>n>>m;
memset(h,-1,sizeof h);
for(int i=0;i<m;i++){
int a,b;
cin>>a>>b;
add(a,b);
din[b]++,dout[a]++;
if(type==1)add(b,a);
}
if(type==1){
for(int i=1;i<=n;i++){
if(din[i]+dout[i]&1){
cout<<"NO\n";
return;
}
}
}
else{
for(int i=1;i<=n;i++){
if(din[i]!=dout[i]){
cout<<"NO\n";
return;
}
}
}
for(int i=1;i<=n;i++){
if(h[i]!=-1){
dfs(i);
break;
}
}
if(cnt<m){x
cout<<"NO\n";
return;
}
cout<<"YES\n";
for(int i=cnt;i;i--)cout<<ans[i]<<" ";
}