無向圖 - 燈泡

Question

我最近開始學習圖形及其不同的遍歷算法，似乎無法拿出這個問題的答案。我真的需要你的幫助，我甚至不知道從哪裏開始。 P.S.昨天是我的生日，因爲這個問題我不想哭。

紐約的一家公司生產汽車用藍色鹵素燈泡。不幸的是，要持續地爲燈泡着色是非常困難的。自然地，包裝看起來相似的燈泡也是非常重要的。爲了將燈泡成對包裝，從裝配線出來的燈泡首先被分成兩組共同類似顏色的燈泡（例如，一組較暗的燈泡，另一組燈泡），然後在每組內形成配對。

由於需求的增加，公司希望僱用更多的員工將燈泡分成兩組。爲了確定申請人是否具備適當的技能來執行這項相當微妙的任務，他們被要求採取這個簡單的測試：給定一組nn燈泡，比較每一對燈泡並確定兩個燈泡是否具有「相似」或「不同」顏色。申請人也可以選擇對每一對說「不確定」。該公司希望聘用符合判斷的申請人。如果可以將n個燈泡分成兩組，使得（i）對於被確定爲「相似」的每個對{a，b}，a（a），則判斷m個判斷（導致「相似」或「不同」）是一致的和b確實屬於同一集合，並且（ii）對於被確定爲「不同」的每對{a，b}，a和b確實屬於不同的集合。

對於具有m個判斷的n個燈泡的給定測試結果，設計O（n + m）時間算法以確定判斷是否一致。在實踐中，應該有最低數量的申請人需要作出的判斷，但是你的算法應該適用於任何整數m≥0。

非常感謝！

Answer 1

我會做這樣的：

1. 與每個燈泡頂點創建一個圖表。如果判斷結果相同，則用紅邊連接頂點，如果判斷結果不同，則用藍邊連接。

2. 使用DFS，BFS或其他方法將圖分區爲由紅色邊連接的頂點集。

3. 檢查每個紅色連接組件內是否有藍色邊緣。如果是這樣，那麼判斷是不一致的。

4. 將每個紅色連接的組件摺疊成一個頂點。這將從圖形中移除所有紅色邊緣。由於（3），它不會去除任何藍色邊緣。此操作反映了限制，即將燈泡分爲兩組時，每個紅色連接組件中的所有燈泡必須位於同一組中。

5. 檢查結果圖是否是雙向的。如果是這樣，那麼你可以一直劃分圖。否則你不能。

這些步驟中的每一步，如果做得對，都適合O（n + m）時間。