做题网站推荐: OpenJudge VIJOS UOJ CF JOYOI CODEVS 洛谷 RQNOJ BZOJ POJ HDU 牛客网

本站题目推荐: 高精度 模拟 排序 递推 贪心 递归 搜索 动态规划 数学 图论 数据结构 签到 实名认证 卡评测举报

输入输出 变量类型 顺序结构 选择结构 循环结构 一维数组 NOIP 资源下载


问题 2809. -- 「一本通 3.7 练习 1」欧拉回路

2809: 「一本通 3.7 练习 1」欧拉回路

时间限制: 1 Sec  内存限制: 256 MB  Special Judge
提交: 26  解决: 10
[上一题][提交][讨论版][状态][下一题]

题目描述

原题来自:UOJ #117

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

一共两个子任务:

  1. 这张图是无向图。(505050 分)

  2. 这张图是有向图。(505050 分)

输入

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

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

接下来 mmm 行中,第 iii 行两个整数 vi,uiv_i, u_ivi,ui,表示第 iii 条边(从 111 开始编号)。保证 1≤vi,ui≤n1 leq v_i, u_i leq n1vi,uin

  1. 如果 t=1t = 1t=1 则表示 viv_iviuiu_iui 有一条无向边。

  2. 如果 t=2t = 2t=2 则表示 viv_iviuiu_iui 有一条有向边。

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

输出

如果不可以一笔画,输出一行 NO

否则,输出一行 YES,接下来一行输出一组方案。

  1. 如果 t=1t = 1t=1,输出 mmm 个整数 p1,p2,,pm。令 e=∣pi∣e = lvert p_i verte=pi,那么 eee 表示经过的第 iii 条边的编号。如果 pip_ipi 为正数表示从 vev_eve 走到 ueu_eue,否则表示从 ueu_eue 走到 vev_eve

  2. 如果 t=2t = 2t=2,输出 mmm 个整数 p1,p2,,pm。其中 pip_ipi 表示经过的第 iii 条边的编号。

提示

样例输入 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

1≤n≤105,0≤m≤2×1051 leq n leq 10^5, 0 leq m leq 2 imes 10^51n105,0m2×105

标签

[上一题][提交][讨论版][状态][下一题]