混合图 (h[u]误写成h[q[u]]……)(一)

2013-01-01 14:48:57 · 作者: · 浏览: 1263

  混合图

  (dizzy.c/cpp/pas)

  【问题描述】

  有一张N个点,M1条有向边,M2条无向边组成的混合图。询问一个给所有无向边定向的方案。使得最终的图中没有环。保证一定有解。

  【输入格式】

  第一行,三个数字N,M1,M2.

  接下来M1+M2行,每行两数字Ai,Bi.表示一条边。

  前M1条是有向边。方向是Ai到Bi.

  【输出格式】

  输出M2行,按输出顺序输出为无向边确定的方向。Ai Bi或Bi Ai.

  有多解时输出任意解。

  【样例输入】

  4 2 3

  1 2

  4 3

  1 3

  4 2

  3 2

  【样例输出】

  1 3

  2 4

  2 3

  【数据规模】

  1<=N<=100 000

  1<=M1,M2<=100000

  拓扑排序即使有重边也成立!