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: