題目：http://poj.org/problem?id=2492
給很多很多蟲蟲的交配關係(無向圖)
問你有沒有可疑的蟲蟲？也就是可能有gay的情形發生
(2011.12.16補上解題報告)
程式碼：http://codepad.org/NgXSzYQm
其實這樣的題目敘述是有點問題的…
題意雖然是二分圖判定
但"圖是二分圖"不全然和"沒有同性戀"等價
說不定一個二分圖裡面其實全部的蟲都是同性阿…
不管那個，反正就是個二分圖判定，作法很多
我是採取DFS染色，起點染1、遇到下一個點染-1，如果發現同色相鄰就中斷
當然也可以BFS、並查集
沒有留言:
張貼留言