尤拉曾經證明在一個無向圖中,如果 每一個點的"度"(與這個點相接的邊的數目)都是偶數,或全部的點中只有兩個是有奇數的"度",這個圖就有一條 一筆畫路徑。就是以一種走法走過所有的邊而每個邊最多只能走一次。
現在請寫一個程式再給定的圖 中找出一條一筆畫路徑,又一個圖中往往有超過一條一筆畫路徑,所以規定只有一條是符合要求的,這一條就是所有路徑中,字典順序最小的(例如1 3 2 4 < 1 3 4 2)
輸入檔可能包含多筆測試資料,每筆測試資料的第一列包含一個正整數M (1 <= M <= 1024),接下來M列每列有兩個數i, j,表示第k條邊連接i與j(1 <= i, j <= 500)。 其中任兩點間可能不止有一條邊相連。M=0代表輸入結束。
對於每筆測試資料請輸出 M+1 行加上一個空白行。每一行有一個正整數, 表示一條一筆畫路徑。可以假設輸入的圖一定有一條一筆畫路徑。
※對不起,測資弄太快了|||
原TIOJ1084 / 94建中校內資訊能力競賽(prob 2)
No. | Testdata Range | Score |
---|---|---|
1 | 0 | 100 |