1084 . 一筆畫問題

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

腦子裝咖哩
想像不出自己 AC 的題目是實作不出來的！雖然想像得出來也不一定可以就是了

User's AC Ratio

88.2% (172/195)

Submission's AC Ratio

28.5% (258/905)

Tags

CKcon 2005-CKcon

Description

尤拉曾經證明在一個無向圖中，如果 每一個點的"度"（與這個點相接的邊的數目）都是偶數，或全部的點中只有兩個是有奇數的"度"，這個圖就有一條 一筆畫路徑。就是以一種走法走過所有的邊而每個邊最多只能走一次。

現在請寫一個程式再給定的圖 中找出一條一筆畫路徑，又一個圖中往往有超過一條一筆畫路徑，所以規定只有一條是符合要求的，這一條就是所有路徑中，字典順序最小的（例如 1 3 2 4<1 3 4 2）

Input Format

輸入檔可能包含多筆測試資料，每筆測試資料的第一列包含一個正整數 M(1≤M≤1024)，接下來 M 列每列有兩個數 i,j，表示第 k 條邊連接 i 與 j (1≤i,j≤500)。 其中任兩點間可能不止有一條邊相連。M=0 代表輸入結束。

Output Format

對於每筆測試資料請輸出 M+1 行加上一個空白行。每一行有一個正整數， 表示一條一筆畫路徑。可以假設輸入的圖一定有一條一筆畫路徑。

Sample Input 1

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

Sample Output 1

1
3
5
1
2
4
                    //這裡有個空白行

Hints

※對不起,測資弄太快了|||

Problem Source

原TIOJ1084 / 94建中校內資訊能力競賽(prob 2)

Subtasks

No. Testdata Range Score
1 0 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 5000 65536 262144 1
Submit
Back to Top