題意: 有散落的一堆珠子，每顆珠子都有兩種顏色，想要把這些珠子串成一條項鍊，且滿足相鄰的兩顆珠子必須以相同的顏色相鄰相連，問是否能串成項鍊。
解法: 是否能串成項鍊跟一筆畫很像，很明顯就是問圖是否存在 Eulerian circuit ，但是並不是直接將珠子當成點，顏色當成邊，而是反過來將顏色當成點，珠子的兩個顏色當成邊，然後檢查是否存在 Eulerian circuit ，且使用DFS輸出結果。
連通的無向圖是歐拉環（存在歐拉迴路）的充要條件是：
TAG: Eulerian circuit, DFS
注意:
程式碼:
沒有留言:
張貼留言
任何意見都樂意傾聽