題目連結:
題目大意:
給你N、M(N < 10000,M < 10 ^ 7),表示一張有N個點的圖。
接下來有M行,每行有兩個數字A、B(1 ≦ A, B ≦ N),代表A跟B有一條邊(A、B間可能不只一條邊)。
求可否用一筆畫的方式走完所有邊。(也就是所有邊只能走一次,保證圖為連通圖)
解題心得:
根據
歐拉的證明,一個連通圖要可以一筆畫畫過的必要條件就是:奇頂點的個數是0或是2。也就是說一個連通圖若只有0或2個頂點,各自連接到的邊數為奇數,則這個圖便保證一定可以一筆畫走過。
然後,在輸入「邊」的時候,用陣列保存數量。最後再迴圈判斷一次即可完成。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。