P3381 - 「一本通 3.7 例 1」欧拉回路

内存限制：256 MB 时间限制：1.000 S

评测方式：文本比较命题人：外部导入

提交：0 解决：0

**原题来自：[UOJ #117](http://uoj.ac/problem/117)** 有一天一位灵魂画师画了一张图，现在要你找出欧拉回路，即在图中找一个环使得每条边都在环上出现恰好一次。一共两个子任务： 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}

有一条有向边。图中可能有重边也可能有自环。

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

t = 1

，输出

m

个整数

p_{1}, p_{2}, \dots, p_{m}

。令

e = | p_{i} |

，那么

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

条边的编号。

YES
1 2 -3

输入样例2

Click

输出样例2

Click

YES
4 1 3 5 2 6

数据范围：

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

LibreOJ

提交提交记录统计露一手!

3381: 「一本通 3.7 例 1」欧拉回路

题目描述

输入

输出

样例输入复制

样例输出复制

提示

输入样例2

输出样例2

来源/分类

3381: 「一本通 3.7 例 1」欧拉回路

题目描述

输入

输出

样例输入 复制

样例输出 复制

提示

输入样例2

输出样例2

来源/分类

样例输入复制

样例输出复制