#34879: 注意DFS的起點


wrr606@gmail.com (Function)

學校 : 國立金門大學
編號 : 133433
來源 : [59.120.127.181]
最後登入時間 :
2024-10-22 14:45:37
d768. 10004 - Bicoloring -- UVa10004 | From: [1.172.159.83] | 發表日期 : 2023-04-23 16:40

規則中有這項

  • 邊是沒有方向性的,也就是說如果節點A可以連到節點B,那麼代表節點B也可以連到節點A。

代表測資中:0 1可以寫成1 0

隨便舉個側資:

4 4
1 0
2 1
3 1
2 3

應輸出為:

NOT BICOLORABLE.

 

所以如果你的寫法是像我一樣用multimap或是vector<pair<int,int> >的資料結構來儲存節點位置,然後用DFS來遍歷的

第一個點有可能不存在,像我的起點設為0,那在剛剛的側資就會錯誤,因為不存在以0為起點的線

所以我設置的起點為 dfs(point.begin()->first);

因為條件中有這項:

  • 圖形是強連通的,也就是說任2節點之間皆有路徑相連。

所以任一點一定至少有一條線連接,因此我的起點只要存在,並開始DFS,就一定可以正確地探索完全部節點

 

參考程式碼:(真的不會寫再看)

https://github.com/wrr606/NotExist_Code/blob/85c4557cab9f2902af4b63a0a72d5bafcd093c21/Zerojudge/Uva%E9%A1%8C%E5%BA%AB/d768.%2010004%20-%20Bicoloring.cpp

 
ZeroJudge Forum