题目描述

有一天一位灵魂画师画了一张图，现在要你找出欧拉回路，即在图中找一个环使得每条边都在环上出现恰好一次。

一共两个子任务：

  1. 这张图是无向图。（50分）
  2. 这张图是有向图。（50分）

输入格式

第一行一个整数 $t$，表示子任务编号。$t \in \{1, 2\}$，如果 $t = 1$ 则表示处理无向图的情况，如果 $t = 2$ 则表示处理有向图的情况。

第二行两个整数 $n, m$，表示图的结点数和边数。

接下来 $m$ 行中，第 $i$ 行两个整数 $v_i, u_i$，表示第 $i$ 条边（从 $1$ 开始编号）。保证 $1 \leq v_i, u_i \leq n$。

  1. 如果 $t = 1$ 则表示 $v_i$ 到 $u_i$ 有一条无向边。
  2. 如果 $t = 2$ 则表示 $v_i$ 到 $u_i$ 有一条有向边。

图中可能有重边也可能有自环。

输出格式

如果不可以一笔画，输出一行 “<samp>NO</samp>”。

否则，输出一行 “<samp>YES</samp>”，接下来一行输出一组方案。

  1. 如果 $t = 1$，输出 $m$ 个整数 $p_1, p_2, \dots, p_m$。令 $e = \lvert p_i \rvert$，那么 $e$ 表示经过的第 $i$ 条边的编号。如果 $p_i$ 为正数表示从 $v_e$ 走到 $u_e$，否则表示从 $u_e$ 走到 $v_e$。
  2. 如果 $t = 2$，输出 $m$ 个整数 $p_1, p_2, \dots, p_m$。其中 $p_i$ 表示经过的第 $i$ 条边的编号。

样例一

input

1
3 3
1 2
2 3
1 3

output

YES
1 2 -3

样例二

input

2
5 6
2 3
2 5
3 4
1 2
4 2
5 1

output

YES
4 1 3 5 2 6

限制与约定

$1 \leq n \leq 10^5, 0 \leq m \leq 2 \times 10^5$

时间限制：$1\texttt{s}$

空间限制：$256\texttt{MB}$

模板题...不过，我没写过欧拉回路....所以也调了好久的样子

主要的思想就是先找一个简单的环，然后从环上的个点在在向外拓展新的环，然后把答案合并在一起倒叙输出

无向图和有向图唯一的不同就是，有向图只需要把操作过的边删掉即可，而无向图需要删除两条边，所以稍微会麻烦一点...

还有一个教训就是不要用vector的eraser，他的复杂度好像是\(O(n)\)啊？

#include<cstdio>  
#include<iostream>  
#include<algorithm>  
#include<cstdlib>  
#include<cstring>
#include<string>
#include<climits>
#include<vector>
#include<cmath>
#include<map>
#include<set>
#define LL long long
 
using namespace std;
 
inline char nc(){
  static char buf[100000],*p1=buf,*p2=buf;
  if (p1==p2) { p2=(p1=buf)+fread(buf,1,100000,stdin); if (p1==p2) return EOF; }
  return *p1++;
}
 
inline void read(int &x){
  char c=nc();int b=1;
  for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
  for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}

int wt,ss[19];
inline void print(int x){
    if (x<0) x=-x,putchar('-'); 
    if (!x) putchar(48); else {
    for (wt=0;x;ss[++wt]=x%10,x/=10);
    for (;wt;putchar(ss[wt]+48),wt--);}
}

int T,n,m,p,d[100010],ru[100010],chu[100010],ans[200010],h[100010];
vector<int> b;
struct data
{
    int x,id;
    data(int a=0,int b=0):x(a),id(b){}
};
vector<data> a[100010];
bool v[200010];

void dfs1(int x,int y)
{
    if (a[x].size()>h[x])
    {
        while (v[abs(a[x][h[x]].id)])
        {
            h[x]++;
            if (h[x]==a[x].size()) break;
        }
        if (a[x].size()>h[x])
        {
            int i=a[x][h[x]].x,j=a[x][h[x]].id;
            h[x]++;v[abs(j)]=1;
            if (i!=y) dfs1(i,y);
            ans[++p]=j;
        }   
    }
    if (a[x].size()>h[x])
    {
        while (v[abs(a[x][h[x]].id)])
        {
            h[x]++;
            if (h[x]==a[x].size()) break;
        }
        if (a[x].size()>h[x]) dfs1(x,x);
    }
}

void dfs2(int x,int y)
{
    if (a[x].size()>h[x])
    {
        int i=a[x][h[x]].x,j=a[x][h[x]].id;
        h[x]++;
        if (i!=y) dfs2(i,y);
        ans[++p]=j;
    }
    if (a[x].size()>h[x]) dfs2(x,x);
}

int main()
{
    read(T);
    if (T==1)
    {
        read(n);read(m);
        int x,y;
        for (int i=1;i<=m;i++)
            read(x),read(y),d[x]++,d[y]++,a[x].push_back(data(y,i)),a[y].push_back(data(x,-i));
        x=0;
        for (int i=1;i<=n;i++)
            if (d[i]%2==1) {puts("NO");return 0;}
            else if (d[i]>0) x=i;
        memset(h,0,sizeof(h));
        p=0;dfs1(x,x);
        if (p<m) {puts("NO");return 0;}
        puts("YES");
        for (int i=m;i>1;i--)
            print(ans[i]),putchar(' ');
        if (m>0) print(ans[1]),puts("");
    }
    else if (T==2)
    {
        read(n);read(m);
        int x,y;
        for (int i=1;i<=m;i++)
            read(x),read(y),chu[x]++,ru[y]++,a[x].push_back(data(y,i)); 
        x=0;
        for (int i=1;i<=n;i++)
            if (ru[i]!=chu[i]) {puts("NO");return 0;}
            else if (ru[i]>0) x=i;
        memset(h,0,sizeof(h));
        p=0;dfs2(x,x);
        if (p<m) {puts("NO");return 0;}
        puts("YES");
        for (int i=m;i>1;i--)
            print(ans[i]),putchar(' ');
        if (m>0) print(ans[1]),puts("");
    }
    return 0;
}