d017: 402 一筆畫遊戲
標籤 :
通過比率 : 0人/0人 (0%) [非即時]
評分方式:
Strictly

最近更新 : 2026-11-17 17:41

內容

1. 題目說明:
請依下列題意進行作答,使輸出值符合題意要求。

2. 設計說明:
(1) 尤拉路徑是圖論(Graph Theory)中被廣為人知的一個經典問題,又被稱為「一筆畫問題」,起源於哥尼斯堡七橋問題;數學家尤拉(Euler)在 1736 年解開了七橋問題並提出相關結論與定理:如果能夠從圖上某一點當作起點出發,找出一條路徑可以通過圖上所有邊恰好一次,就好像用畫筆可以連續地畫過該圖形的所有邊,該路徑就稱為「尤拉路徑(Euler path)」。

(2) 以下是尤拉對於一筆畫問題的重點結論:
「一個連通圖中,所有節點的分支度都是偶數,或只有 2 個節點的分支度是奇數,則該圖就可以用一筆畫完成;否則無法一筆畫。」

(3) 一個無向圖(Undirected Graph)通常表示為 G=(V,E),其中 V 為節點(Vertex)的集合,E 為邊(Edge)的集合,且任一個邊是由兩個相連接的節點所構成,當標示為 (a,b) 即表示節點 a 與 b 之間有邊連接。

(4) 請設計一支程式,可以讀取一個無向圖的資料(邊的列表),然後判斷該圖形是否能夠一筆畫完成,並輸出圖形的相鄰矩陣結果(注意:題目給的圖形一定是「連通圖」)。

提示:任一節點的「分支度(Degree)」為該節點連接的邊數、亦即是對外所連接的節點數。
提示:「連通圖(Connected Graph)」中的任兩個節點必存在一條路徑相通;反之則為「非連通圖」。
提示:可使用「二維陣列(Two-Dimensional Array)」資料結構來實作「相鄰矩陣(Adjacency Matrix)」以紀錄圖形中節點與節點的關係(邊)。

輸入說明

第 1 列:包含兩個正整數 M、N,並以半形空白間隔,其中 M 為節點數、N 為邊數。
第 2~N+1 列:每一列包含兩個正整數 a、b,並以半形空白間隔,代表圖形的某一個邊連接節點 a 與 b,且 1 ≤ a, b ≤ M。

輸出說明

第 1 列:若圖形可以「一筆畫完成」,則輸出「YES」;否則輸出「NO」。
第 2~M+1 列:輸出圖形的相鄰矩陣,共有 M 列由 0 與 1 所構成的資料列,每一列有 M 個數字,請使用「1」表示列、行相對應的節點之間有邊;使用「0」表示沒有對應邊的存在,每個數字之間須以半形空白間隔。

範例輸入 #1
3 3
1 2
1 3
3 2
範例輸出 #1
YES
0 1 1
1 0 1
1 1 0
範例輸入 #2
5 8
1 2
1 3
1 4
1 5
2 5
3 2
3 4
5 4
範例輸出 #2
NO
0 1 1 1 1
1 0 1 0 1
1 1 0 1 0
1 0 1 0 1
1 1 0 1 0
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (20%): 1.0s , <1K
公開 測資點#1 (20%): 1.0s , <1K
公開 測資點#2 (20%): 1.0s , <1K
公開 測資點#3 (20%): 1.0s , <1K
公開 測資點#4 (20%): 1.0s , <1K
提示 :
標籤:
出處:
[管理者:
zero (管理員)
]


編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」