29 . 一筆畫問題
TopCoder
Tags
Description
一筆畫問題是一個經典的圖論問題，用圖論術語來描述的話，就是給定一張圖，問存不存在一條從 $s$ 到 $t$ 的路徑，滿足所有邊都恰被遍歷一次（點則可以被重複遍歷），這樣的路徑又被稱為「歐拉路徑」。
當然，一筆畫問題在有向圖上也是可以解決的！因此，現在給你一張 $N$ 點 $M$ 邊的有向圖，請你先判斷這張有向圖有幾種 $s=1, t=N$ 的歐拉路徑，並在有至少一種時，輸出一條從 $1$ 到 $N$ 的歐拉路徑。
不過，因為歐拉路徑的數量可能很多，所以假設總共有 $k$ 種歐拉路徑，你只需要輸出 $\min(k, 2)$ 就可以了。
- 兩條歐拉路徑不同，若且唯若他們使用邊的順序不同。
Input Format
輸入首行有兩個整數 $N, M$，代表點的個數和邊的個數。
接下來有 $M$ 行，第 $i$ 行兩個整數 $u_i, v_i$，代表這張有向圖的第 $i$ 條邊是從 $u_i$ 指到 $v_i$。
- $2 \leq N \leq 3\times 10^ 5$
- $1 \leq M \leq 3\times 10^ 5$
- $1 \leq u_i, v_i \leq N, u_i \neq v_i$
- $(u_i, v_i) \neq (u_j, v_j),\ \forall i \neq j$
Output Format
假設這張有向圖從 $s$ 走到 $t$ 的歐拉路徑有 $k$ 種，首行輸出 $\min(k, 2)$。
若 $k>0$，接下來輸出 $M$ 行，第 $i$ 行兩個整數 $a_i, b_i$ 以單一空格隔開，代表你輸出的歐拉路徑中使用的第 $i$ 條邊是從 $a_i$ 走到 $b_i$。此時，只要你輸出的歐拉路徑合法，也就是滿足
- $a_1 = 1$, $b_M = N$
- $b_i = a_{i + 1},\ \forall 1\leq i < M$
- 你輸出的邊集合與輸入的邊集合相同
就會視為正確。
Sample Input 1
5 5
1 2
2 3
3 4
4 1
1 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
1 2
2 3
3 4
4 1
1 5
Sample Input 2
3 2
1 3
2 1
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
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
1 2
2 3
3 1
1 4
4 1
1 5
Hints
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~2 | 範例測資。 | 0 |
| 2 | 3~15 | 歐拉路徑的個數 $\leq 1$。 | 40 |
| 3 | 0~36 | 無特別限制。 | 60 |