嗨嗨嗨嗨嗨
是二分圖唷ㄏㄏ
連結：TIOJ1209 圖論 之 二分圖測試
題目：
給你一些點和一些邊，請問它是不是一張二分圖(Bipartite Graph)呢?
(定義詳見題目敘述)
(定義詳見題目敘述)
做法：
在碰到二分圖最大匹配以前還不曉得什麼是二分圖
但聽過樹都是二分圖
但想了想有環也可能會是二分圖，例如1-2, 1-3, 2-4, 3-4，1和4一團，2和3一團
這時可以發現如果從一個點開始遍歷，同一個點的深度不是奇數就是偶數
若存在點深度有偶數又有奇數，則它不是二分圖，有奇環
那就解決啦! 一次DFS檢查，搞定
有些人好像都會說著色法，把點著上兩個不同的顏色，每個點的鄰居顏色都要跟自己不一樣
也就是分成兩群，嗯
code:
沒有留言:
張貼留言