定義

如果圖G中的一個路徑包括每個邊恰好一次，則該路徑稱為歐拉路徑(Euler path)。
如果一個回路是歐拉路徑，則稱為歐拉回路(Euler circuit)。
（換句話說，如果從一個點(diǎn)出發(fā)，經(jīng)過每條邊一次且僅一次，回到了原點(diǎn)，就稱這條路徑為歐拉回路）

思路

首先讀入后判斷符不符合歐拉回路存在的條件：
有向圖每個點(diǎn)入度=出度
無向圖每個點(diǎn)入度/出度為偶數(shù)
代碼：

  if(p==1)
  {
    for(int i=1; i<=n; i++)
      if((in[i]+out[i])%2)
      {
        printf("NO\n");
        return 0;
      }
  }
  else
  {
    for(int i=1; i<=n; i++)
      if(in[i]!=out[i])
      {
        printf("NO\n");
        return 0;
      }
  }

然后再亂搜索就行了（記得記錄和判重)
代碼：

void dfs(int k)
{
  for(int &i=head[k]; i; i=a[i].nxt)
  {
    int v=(p==1?i/2:i-1),num=i%2;
    if(flag[v]) continue;
    flag[v]=1,dfs(a[i].to);
  }
}

這里，p=1時候，是無向圖，p=2時候是有向圖。

例題

一本通1527
十分基本，就加了個輸出路徑。

#include <bits/stdc++.h>
using namespace std;
struct node
{
  int to,nxt;
} a[400005];
int n,m,p,out[100005],in[100005],x,y;
int head[100005],cnt=1,ans[200005],tot;
bool flag[400005];
void add(int x,int y)
{
  a[++cnt].to=y,a[cnt].nxt=head[x],head[x]=cnt;
}
void dfs(int k)
{
  for(int &i=head[k]; i; i=a[i].nxt)
  {
    int v=(p==1?i/2:i-1),num=i%2;
    if(flag[v]) continue;
    flag[v]=1,dfs(a[i].to);
    if(p==1) ans[++tot]=(num?-v:v);
    else ans[++tot]=v;
  }
}
int main()
{
  scanf("%d%d%d",&p,&n,&m);
  for(int i=1; i<=m; i++)
  {
    scanf("%d%d",&x,&y),out[x]++,in[y]++;
    if(p==1) add(x,y),add(y,x);
    else add(x,y);
  }
  if(p==1)
  {
    for(int i=1; i<=n; i++)
      if((in[i]+out[i])%2)
      {
        printf("NO\n");
        return 0;
      }
  }
  else
  {
    for(int i=1; i<=n; i++)
      if(in[i]!=out[i])
      {
        printf("NO\n");
        return 0;
      }
  }
  for(int i=1; i<=n; i++)
    if(head[i])
    {
      dfs(i);
      break;
    }
  if(tot!=m)
  {
    printf("NO\n");
    return 0;
  }
  printf("YES\n");
  for(int i=m; i>0; i--) printf("%d ",ans[i]);
  return 0;
}

小結(jié)

歐拉回路，只要先判斷，然后搜索就行了，判重是比較重要的。

完結(jié)撒花?。?！
別忘了點(diǎn)贊，關(guān)注，謝謝?。?/p>