ETH官方钱包

切換
舊版
前往
大廳
主題

ZeroJudge - b924: kevin 愛畫畫 解題心得

Not In My Back Yard | 2018-09-04 22:12:54 | 巴幣 0 | 人氣 407

題目連結:

題目大意:
給你N、M(N < 10000,M < 10 ^ 7),表示一張有N個點的圖。

接下來有M行,每行有兩個數字A、B(1 ≦ A, B ≦ N),代表A跟B有一條邊(A、B間可能不只一條邊)。

求可否用一筆畫的方式走完所有邊。(也就是所有邊只能走一次,保證圖為連通圖)

解題心得:
根據歐拉的證明,一個連通圖要可以一筆畫畫過的必要條件就是:奇頂點的個數是0或是2。也就是說一個連通圖若只有0或2個頂點,各自連接到的邊數為奇數,則這個圖便保證一定可以一筆畫走過。

然後,在輸入「邊」的時候,用陣列保存數量。最後再迴圈判斷一次即可完成。


此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作