MediumRating 1795
886. Possible Bipartition
depth-first-searchbreadth-first-searchunion-findgraph
解題說明
Possible Bipartition
題目描述： 有 n 個人，給定一些不喜歡對 (a, b) 表示 a 和 b 互相不喜歡。能否將所有人分成兩組，使得每對不喜歡的人在不同組？
解題思路：
- 這本質上是一個二分圖判定問題：把不喜歡的關係建成無向圖，問圖是否為二分圖。
- BFS/DFS 染色：對圖中每個連通分量進行二染色。從任意未染色節點開始，染色為 0。對其所有鄰居染色為 1。如果發現鄰居已經被染成相同顏色，則不是二分圖。
- 所有連通分量都是二分圖，答案才為 true。
- 也可以用 Union-Find：對每個節點，把它的所有「敵人」放到同一組。
C++ 解法
複雜度分析
時間複雜度：O(n + E) — n 為人數，E 為不喜歡對的數量。每個節點和邊只處理一次
空間複雜度：O(n + E) — 圖的鄰接表和顏色陣列
虛擬碼
1. Build undirected graph from dislikes pairs
2. Initialize color array with -1 (uncolored)
3. For each uncolored node i:
a. BFS from i, color it 0
b. For each neighbor v of current node u:
- If uncolored: color v = 1 - color[u], add to queue
- If same color as u: return false (odd cycle found)
4. Return true (all components are bipartite)其他解法
-
Union-Find 方法：對每個節點 u，將 u 的所有鄰居合併到同一組（「敵人的敵人是朋友」）。如果發現 u 和某個鄰居在同一組，返回 false。時間複雜度 O(E * α(n))，接近線性。
-
DFS 染色：與 BFS 類似，用遞迴 DFS 實現。代碼更簡潔但可能受遞迴深度限制。對於稀疏圖效果相同。
延伸思考
- 如果要分成三組（而不是兩組），使得不喜歡的人在不同組，如何判斷？（提示：三染色問題是 NP-Complete）
- 如果不是判斷可行性，而是要輸出一種分組方案呢？
- 如果可以動態增加或刪除不喜歡關係，如何高效維護答案？