886. Possible Bipartition
給你一個數字n表示人數,一個陣列表示a討厭b,找出是否有方法可以將人分成兩組
而且同一組沒有不仲。
Example:
Input: n = 4, dislikes = [[1,2],[1,3],[2,4]]
Output: true
Explanation: group1 [1,4] and group2 [2,3].
Input: n = 3, dislikes = [[1,2],[1,3],[2,3]]
Output: false
思路:
1.想了很久想不出來,看了一下討論才知道是一個著色問題,先建立一個有向圖把
所有討厭的人都雙向連結。
2.從隨便一個點開始用dfs上色,0表示未著色,1和-1分別表示一種顏色,每次上色
都檢查鄰近的點的顏色是否都不同,若出現相同顏色表示討厭的人被分在一起了返
回false。
3.如果整個圖上色完都沒有衝突返回true。
Java Code: