解决方案


方法:深度优先搜索

思路

尝试将每个人分配到一个组是很自然的想法。假设第一组中的人是红色,第二组中的人是蓝色。

如果第一个人是红色的,那么这个人不喜欢的人必须是蓝色的。然后,任何不喜欢蓝色人的人都是红色的,那么任何不喜欢红色人的人都是蓝色的,依此类推。

如果在任何时候存在冲突,那么这个任务是不可能的完成的,因为从第一步开始每一步都符合逻辑。如果没有冲突,那么着色是有效的,所以答案是 true

算法

考虑由给定的 “不喜欢” 边缘形成的 N 人的图表。我们要检查这个图的每个连通分支是否为二分的。

对于每个连通的部分,我们只需试着用两种颜色对它进行着色,就可以检查它是否是二分的。如何做到这一点:将任一结点涂成红色,然后将它的所有邻居都涂成蓝色,然后将所有的邻居的邻居都涂成红色,以此类推。如果我们将一个红色结点涂成蓝色(或蓝色结点涂成红色),那么就会产生冲突。

复杂度分析

  • 时间复杂度:,其中 不喜欢 dislikes 的长度。

  • 空间复杂度: