🪴 Edwin Aze's Blog

最近文章

最近笔记

欧拉回路

6分钟阅读

欧拉回路 DFS T3 #10105. 「一本通 3.7 例 1」欧拉回路 - 题目 - LibreOJ (loj.ac) 有一天一位灵魂画师画了一张图，现在要你找出欧拉回路，即在图中找一个环使得每条边都在环上出现恰好一次。 一共两个子任务：

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

输入格式

第一行一个整数 ，表示子任务编号。 ，如果 则表示处理无向图的情况，如果 则表示处理有向图的情况。

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

接下来 行中，第 行两个整数 ，表示第 条边（从 开始编号）。保证 。

  1. 如果 则表示 到 有一条无向边。
  2. 如果 则表示 到 有一条有向边。

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

输出格式

如果不可以一笔画，输出一行 NO。 否则，输出一行 YES，接下来一行输出一组方案。

  1. 如果 ，输出 个整数 。令 ，那么 表示经过的第 条边的编号。如果 为正数表示从 走到 ，否则表示从 走到 。
  2. 如果 ，输出 个整数 。其中 表示经过的第 条边的编号。

样例 1

输入

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

输出

YES
4 1 3 5 2 6

数据范围与提示

思路

求欧拉回路的话, 需要先判断是否有解： 1）有向图时, 只有所有点的入度等于出度才算有解 2）无向图时, 所有点的度数都是偶数才算有解

加边时统计度数, 然后再DFS搜索路径, 如果路径长度小于m, 即没有搜到所有边, 那么也算无解。

搜的时候若朴素暴力搜：

dfs()
	for (i=h[u] ; i = ne[i])
		if(used[i]) 
			h[u] = ne[i]
			continue
		h[u] = ne[i]
		if(type == 1) used[i ^ 1] = true;
		dfs(e[i])

因为DFS会先搜到最低端然后再回溯, 而标记边时只能标记已经搜过的, 那么回溯之后有可能拐到之前的边, 极端情况下还是 的复杂度。

这里可以在枚举时直接让 , 边缩边搜, 就是 复杂度了。 如果碰到之前搜过的边 则直接 跳过即可。若没搜过则加入到结果序列中, 注意这里是添加编号, 且若为无向边则只添加一条边。 有向边的编号就是 , 而无向图的编号则是 , 题目中还要求如果是反向边需要输出负数, 因为正反两条边添加是一起的, 第一条, 第二条 故正向边都会是奇数, 而反向边都是偶数。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;
const int N = 1e5 + 10, M = 4e5 + 10;
int h[N], ne[M], e[M], idx;
int n, m;
int type;
int din[N], dout[N];
bool used[M];
int cnt, res[M];
 
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;)
    {
        if (used[i])
        {
            i = ne[i];
            continue;
        }
        used[i] = true;
 
        int t;
        if (type == 1)
        {
            used[i ^ 1] = true;
            t = i / 2 + 1;
            if (i & 1)
                t = -t;
        }
        else
            t = i + 1;
        int j = e[i];
        i = ne[i];
 
        dfs(j);
        res[++cnt] = t;
    }
}
 
int main()
{
    memset(h, -1, sizeof h);
    cin >> type;
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int a, b;
        cin >> 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)
            {
                cout << "NO\n";
                return 0;
            }
    }
    else if (type == 2)
    {
        for (int i = 1; i <= n; i++)
            if (din[i] != dout[i])
            {
                cout << "NO\n";
                return 0;
            }
    }
    for (int i = 1; i <= n; i++)
        if (h[i] != -1)
        {
            dfs(i);
            break;
        }
    if (cnt < m)
    {
        cout << "NO\n";
        return 0;
    }
    cout << "YES\n";
    for (int i = cnt; i; i--)
        cout << res[i] << " ";
 
    return 0;
}

反向链接