中的圖形問題

Question

我奮力解決以下問題

http://uva.onlinejudge.org/external/1/193.html

但是我不是能得到一個快速的解決方案。

被別人的時候所看到，應該有最大的N^2的複雜性的解決方案

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problemid=129&page=problem_stats

我能得到一些幫助？

Answer 1

您只能以指數複雜度解決這個問題，但這並不像聽起來那麼糟糕，因爲在實踐中，您將能夠避免很多錯誤的決策，從而顯着減少算法的運行時間。

簡而言之，您必須從節點運行DF搜索，並儘量爲儘可能多的黑色節點着色。如果您位於具有相鄰黑節點的節點上，則該節點只能是白色。繼續爲着色特定節點的每一種可能性做這件事。

如果您無法弄清楚，請查看我通過使用Google搜索問題名稱找到的這兩個代碼片段：one和two。作者說他們得到AC，但我沒有測試它們。然而他們看起來正確。

Answer 2

它正在解決稱爲最大團的問題，也稱爲最大獨立集或最大穩定集。這是NP-Complete。我知道的最小的代碼是Cliquer：http://users.tkk.fi/pat/cliquer.html

如果你正在爲教育目的而自己編寫自己的代碼，那麼一次深度優先搜索染色節點黑色並退回DFS（如果兩個黑色節點觸摸。

最簡單的代碼解決方案是實現一個二進制計數器並嘗試所有2^n個可能性。

Answer 3

Bron–Kerbosch algorithm

我已經解決了在Facebook上的難題類似的問題，我用在B-K算法中了點。