Oj.Nbdp.Net
初赛题库
问题
状态
排名
团队
题解
课程
Login
问题 4047 --【例题1】欧拉回路(UOJ117)
4047: 【例题1】欧拉回路(UOJ117)
警告!
题目
状态
题解(1)
题目描述
有一天一位灵魂画师画了一张图,现在要你找出欧拉回路,即在图中找一个环使得每条边都在环上出现恰好一次。 一共两个子任务: 这张图是无向图。(50 分) 这张图是有向图。(50 分)
输入
第一行一个整数 t,表示子任务编号。t∈{1,2},如果 t=1 则表示处理无向图的情况,如果 t=2 则表示处理有向图的情况。 第二行两个整数 n,m,表示图的结点数和边数。 接下来 m 行中,第 i 行两个整数 vi,ui ,表示第 i 条边(从 1 开始编号)。保证 1≤vi,ui≤n。 如果 t=1 则表示 vi 到 ui 有一条无向边。 如果 t=2 则表示 vi 到 ui 有一条有向边。 图中可能有重边也可能有自环。
输出
如果不可以一笔画,输出一行 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
复制
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≤10
5
,0≤m≤2×10
5
发表题解
序号
标题
作者
发表时间
费用
订购数
操作
题目信息
提交
难度
提高+/省选-
标签
点击显示
if ($pr_flag) { ?>
递交数
10
已通过
5
} ;?>
通过率
50%
时间限制
1 秒
内存限制
128 MB
来源
一本通(提高篇)
收藏
标签云
模拟
数学与数论
动态规划
贪心
字符串
排序
枚举
数组与串
深搜
高精度
循环结构
递推
递归
二分三分
宽搜
背包
质数
线段树
分治
N进制
图论
队列
最短路
堆
树
并查集
栈
状态压缩
分支结构
几何
博弈论
生成树
顺序结构
离散化
hash表
位运算
单调队列
树状数组
KMP
字典树
二分图
数学期望
AC自动机
树链剖分
差分约束
数位动态规划
函数与过程
网络流
单调栈
前缀和