回『UVa 題庫』
n817. 11396 - Claw Decomposition
標籤 :
通過比率 : 3人/5人 ( 60% ) [非即時]
評分方式：
Tolerant

最近更新 : 2024-06-04 14:23

內容

爪子被定義為鳥類、某些爬行動物和某些哺乳動物的每個趾端的尖彎指甲。然而，如果你是圖論愛好者，你可能會理解如下圖所示的特殊類別圖，稱之為爪子。如果你更關注圖論術語，你可能會將爪子定義為 K 1,3。

讓我們暫時離開定義，來看看這個問題。你將被給予一個簡單的無向圖，其中每個頂點的度數為3。你需要判斷該圖是否可以被分解為爪子。

為了清楚起見，圖的分解是一個子圖列表，使得每條邊僅出現在列表中的一個子圖中。

輸入說明

輸入文件中將包含多組測試案例。每組案例的開始是圖中的頂點數量 V (4 ≤ V ≤ 300)。接著是邊列表。列表中的每行包含兩個整數 a 和 b，分別是邊的兩個端點 (1 ≤ a, b ≤ V)。邊列表以一行包含一對 '0' 結束。輸入的結束由 V = 0 的案例表示。這個案例不應被處理。

輸出說明

對於輸入中的每個案例，如果該圖能夠被分解成爪形圖，則輸出 'YES'，否則輸出 'NO'。

範例輸入 #1 
4
1 2
1 3
1 4
2 3
2 4
3 4
0 0
6
1 2
1 3
1 6
2 3
2 5
3 4
4 5
4 6
5 6
0 0
0
範例輸出 #1 
NO
NO
測資資訊：
記憶體限制： 64 MB
公開 測資點#0 (50%): 1.0s , <1K
公開 測資點#1 (50%): 1.0s , <1M
提示 ：
標籤:
出處:
UVA [管理者： ig99lp33lp33 (위즈원) ]

本題狀況 本題討論 排行

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