链接:http://uoj.ac/problem/117

题目描述

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

一共两个子任务:

  1. 这张图是无向图。(50分)
  2. 这张图是有向图。(50分)

输入格式

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

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

接下来  行中,第  行两个整数 ,表示第  条边(从  开始编号)。保证 。

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

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

输出格式

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

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

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

    input

    output

    样例二

    input

    output

    限制与约定

    算法基于原理:在一个欧拉回路中如果我们删除一个欧拉回路不会妨碍剩下的也构成一个欧拉回路

    有向图欧拉回路有解条件:所有出度等于入度 无向图有解条件:度为偶数

  4. 需要类似当前弧优化一样的东西
  5. 倒序输出 mdzz

  6.  
分类: 欧拉图

elijahqi

退役了 现在在商院 偶尔打CF,有时有ACM regional也去玩一下

发表评论