欧拉路 之 欧拉回路

定义

如果图G中的一个路径包括每个边恰好一次，则该路径称为欧拉路径(Euler path)。
如果一个回路是欧拉路径，则称为欧拉回路(Euler circuit)。
（换句话说，如果从一个点出发，经过每条边一次且仅一次，回到了原点，就称这条路径为欧拉回路）

思路

首先读入后判断符不符合欧拉回路存在的条件：
有向图每个点入度=出度
无向图每个点入度/出度为偶数
代码：

  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;
}

小结

欧拉回路，只要先判断，然后搜索就行了，判重是比较重要的。

完结撒花！！！
别忘了点赞，关注，谢谢！！