29 . 一筆畫問題

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido
主唱太拼命了

User's AC Ratio

90.2% (37/41)

Submission's AC Ratio

30.5% (53/174)

Tags

ioicamp ioicamp-2024

Description

一筆畫問題是一個經典的圖論問題，用圖論術語來描述的話，就是給定一張圖，問存不存在一條從 s 到 t 的路徑，滿足所有邊都恰被遍歷一次（點則可以被重複遍歷），這樣的路徑又被稱為「歐拉路徑」。

當然，一筆畫問題在有向圖上也是可以解決的！因此，現在給你一張 N 點 M 邊的有向圖，請你先判斷這張有向圖有幾種 s=1,t=N 的歐拉路徑，並在有至少一種時，輸出一條從 1 到 N 的歐拉路徑。

不過，因為歐拉路徑的數量可能很多，所以假設總共有 k 種歐拉路徑，你只需要輸出 min(k,2) 就可以了。

  • 兩條歐拉路徑不同，若且唯若他們使用邊的順序不同。

Input Format

輸入首行有兩個整數 N,M，代表點的個數和邊的個數。

接下來有 M 行，第 i 行兩個整數 ui,vi，代表這張有向圖的第 i 條邊是從 ui 指到 vi。

  • 2≤N≤3×105
  • 1≤M≤3×105
  • 1≤ui,vi≤N,ui≠vi
  • (ui,vi)≠(uj,vj), ∀i≠j

Output Format

假設這張有向圖從 s 走到 t 的歐拉路徑有 k 種，首行輸出 min(k,2)。

若 k>0，接下來輸出 M 行，第 i 行兩個整數 ai,bi 以單一空格隔開，代表你輸出的歐拉路徑中使用的第 i 條邊是從 ai 走到 bi。此時，只要你輸出的歐拉路徑合法，也就是滿足

  • a1=1, bM=N
  • bi=ai+1, ∀1≤i<M
  • 你輸出的邊集合與輸入的邊集合相同

就會視為正確。

Sample Input 1

5 5
1 2
2 3
3 4
4 1
1 5

Sample Output 1

1
1 2
2 3
3 4
4 1
1 5

Sample Input 2

3 2
1 3
2 1

Sample Output 2

0

Sample Input 3

5 6
1 2
1 4
1 5
2 3
3 1
4 1

Sample Output 3

2
1 2
2 3
3 1
1 4
4 1
1 5

Hints

Problem Source

IOICamp 2024 Day3 pD

Subtasks

No. Testdata Range Constraints Score
1 0~2 範例測資 0
2 3~15 歐拉路徑的個數 ≤1 40
3 0~36 無額外限制 60

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2000 262144 65536 1 3
1 2000 262144 65536 1 3
2 2000 262144 65536 1 3
3 2000 262144 65536 2 3
4 2000 262144 65536 2 3
5 2000 262144 65536 2 3
6 2000 262144 65536 2 3
7 2000 262144 65536 2 3
8 2000 262144 65536 2 3
9 2000 262144 65536 2 3
10 2000 262144 65536 2 3
11 2000 262144 65536 2 3
12 2000 262144 65536 2 3
13 2000 262144 65536 2 3
14 2000 262144 65536 2 3
15 2000 262144 65536 2 3
16 2000 262144 65536 3
17 2000 262144 65536 3
18 2000 262144 65536 3
19 2000 262144 65536 3
20 2000 262144 65536 3
21 2000 262144 65536 3
22 2000 262144 65536 3
23 2000 262144 65536 3
24 2000 262144 65536 3
25 2000 262144 65536 3
26 2000 262144 65536 3
27 2000 262144 65536 3
28 2000 262144 65536 3
29 2000 262144 65536 3
30 2000 262144 65536 3
31 2000 262144 65536 3
32 2000 262144 65536 3
33 2000 262144 65536 3
34 2000 262144 65536 3
35 2000 262144 65536 3
36 2000 262144 65536 3
Submit
Back to Top