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,且关系不重复。

自建示例

偶数环可以交替分组:

输入:n = 4, dislikes = [[1,2],[2,3],[3,4],[1,4]]
输出:true
解释:可以把人物 1、3 放入一组,把人物 2、4 放入另一组,所有不喜欢关系都跨越两个组。

五人奇环无法二分:

输入:n = 6, dislikes = [[1,2],[2,3],[3,4],[4,5],[1,5]]
输出:false
解释:人物 1 至 5 构成长度为 5 的奇环,沿环交替分组后最后一条关系仍会连接同组两人,因此无法只分成两组;没有关系的人物 6 不会改变结论。