0886. Possible Bipartition ======================================================================================================================== 题目信息 -------- :题号: 0886 :难度: Medium :主题: 无向图、二分组、不相容关系 :原题: `LeetCode 0886 `_ :重点: 人员编号从 1 开始;每对互相不喜欢的人必须被分到不同组,所有人员都要恰好属于一个组 题目重述 -------- 有 ``n`` 个人,编号为 ``1`` 至 ``n``。数组 ``dislikes`` 中的每项 ``[a, b]`` 表示人物 ``a`` 与人物 ``b`` 互相不喜欢,这种约束没有方向。 请判断能否把全部人员划分为两个组,使每个人恰好属于其中一组,并且每一对互相不喜欢的人都位于不同组。两组人数不要求相等,没有不喜欢关系的人可以放入任意一组。 ``1 <= n <= 2000``,``0 <= dislikes.length <= 10^4``;每对编号满足 ``1 <= a < b <= n``,且关系不重复。 自建示例 -------- 偶数环可以交替分组: .. code-block:: text 输入:n = 4, dislikes = [[1,2],[2,3],[3,4],[1,4]] 输出:true 解释:可以把人物 1、3 放入一组,把人物 2、4 放入另一组,所有不喜欢关系都跨越两个组。 五人奇环无法二分: .. code-block:: text 输入:n = 6, dislikes = [[1,2],[2,3],[3,4],[4,5],[1,5]] 输出:false 解释:人物 1 至 5 构成长度为 5 的奇环,沿环交替分组后最后一条关系仍会连接同组两人,因此无法只分成两组;没有关系的人物 6 不会改变结论。