题面

【题目描述】
原题来自：UOJ #117
有一天一位灵魂画师画了一张图，现在要你找出欧拉回路，即在图中找一个环使得每条边都在环上出现恰好一次。
一共两个子任务：
这张图是无向图。（50 分）
这张图是有向图。（50 分）
【输入】
第一行一个整数 t，表示子任务编号。t∈{1,2}，如果 t=1 则表示处理无向图的情况，如果 t=2 则表示处理有向图的情况。
第二行两个整数 n,m，表示图的结点数和边数。
接下来 m 行中，第 i 行两个整数 vi,ui ，表示第 i 条边（从 1 开始编号）。保证 1≤vi,ui≤n。
如果 t=1 则表示 vi 到 ui 有一条无向边。
如果 t=2 则表示 vi 到 ui 有一条有向边。
图中可能有重边也可能有自环。
【输出】
如果不可以一笔画，输出一行 NO。
否则，输出一行 YES，接下来一行输出一组方案。
如果 t=1，输出 m 个整数 p1,p2,…,pm 。令 e=|pi|，那么 e 表示经过的第 i 条边的编号。如果 pi为正数表示从 ve 走到 ue ，否则表示从 ue 走到 ve 。
如果 t=2，输出 m 个整数 p1,p2,…,pm 。其中 pi 表示经过的第 i 条边的编号。
【输入样例】
1
3 3
1 2
2 3
1 3
【输出样例】
YES
1 2 -3
【提示】
样例输入 2
2
5 6
2 3
2 5
3 4
1 2
4 2
5 1
样例输出 2
YES
4 1 3 5 2 6
数据范围与提示：
1≤n≤105,0≤m≤2×105
一句话题意：求无向图/有向图中的欧拉回路。

思路

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

  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);
    if(p==1) ans[++tot]=(num?-v:v);
    else ans[++tot]=v;
  }
}

代码

上代码：

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

小结

十分基础，记住条件，乱搜就行了
欢迎私信~~

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