1184. 欧拉回路

给定一张图，请你找出欧拉回路，即在图中找一个环使得每条边都在环上出现恰好一次。

输入格式

第一行包含一个整数 t，t∈{1,2}，如果 t=1，表示所给图为无向图，如果 t=2，表示所给图为有向图。

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

接下来 m 行中，第 i 行两个整数 vi,ui，表示第 i 条边（从 1 开始编号）。

如果 t=1 则表示 vi 到 ui 有一条无向边。
如果 t=2 则表示 vi 到 ui 有一条有向边。
图中可能有重边也可能有自环。

点的编号从 1 到 n。

输出格式

如果无法一笔画出欧拉回路，则输出一行：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≤n≤105,
0≤m≤2×105

输入样例1：

1
3 3
1 2
2 3
1 3

输出样例1：

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

代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 100010, M = 400010;

int type;
int n, m;
int h[N], e[M], ne[M], idx;
bool used[M];
vector<int> res;
int din[N], dout[N];
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 != -1; i = h[u]) // 不能i=ne[i], 因为可能在dfs中ne[i]已经删除， 虽然有used但是还是会进入循环 m个自环的情况则复杂度剧增 所以必须指向最新的h[u]
    {
    
        if (used[i]) // 若访问过则删除
        {
    
            h[u] = ne[i];
            continue;
        }

        used[i] = 1;
        if (type == 1)
            used[i ^ 1] = true; // 使得上面的判断有意义 无向边可能访问了没删除

        int t;
        if (type == 1)
        {
    
            t = i / 2 + 1;
            if (i & 1)
                t = -t;
        }
        else
            t = i + 1;

        int j = e[i];
        h[u] = ne[i];

        dfs(j);
        res.push_back(t);// 求路径上的边顺序
    }
}

int main()
{
    
    scanf("%d", &type);
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof(h));

    for (int i = 0; i < m; i++)
    {
    
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
        if (type == 1)
            add(b, a);
        din[b]++, dout[a]++;
    }

    if (type == 1)
    {
    
        for (int i = 1; i <= n; i++)
        {
    
            if (din[i] + dout[i] & 1) // 无向边
            {
    
                puts("NO");
                return 0;
            }
        }
    }
    else
    {
    
        for (int i = 1; i <= n; i++)
        {
    
            if (din[i] != dout[i]) // 有向边
            {
    
                puts("NO");
                return 0;
            }
        }
    }

    for (int i = 1; i <= n; i++)
    {
    
        if (h[i] != -1)
        {
    
            dfs(i);
            break;
        }
    }

    if (res.size() < m)
    {
    
        puts("NO");
        return 0;
    }

    puts("YES");
    for (int i = res.size() - 1; i >= 0; i--)
        printf("%d ", res[i]);
    puts("");

    return 0;
}