一、题目
给定一组?n?人（编号为?1, 2, ..., n），?我们想把每个人分进任意大小的两组。每个人都可能不喜欢其他人，那么他们不应该属于同一组。
给定整数?n?和数组?dislikes?，其中?dislikes[i] = [ai, bi]?，表示不允许将编号为?ai?和??bi的人归入同一组。当可以用这种方法将所有人分进两组时，返回?true；否则返回?false。
二、示例
2.1> 示例 1：
【输入】n = 4, dislikes = [[1,2],[1,3],[2,4]]
【输出】true
【解释】group1 [1,4], group2 [2,3]
2.2> 示例 2：
【输入】n = 3, dislikes = [[1,2],[1,3],[2,3]]
【输出】false
2.3> 示例 3：
【输入】n = 5, dislikes = [[1,2],[2,3],[3,4],[4,5],[1,5]]
【输出】false
提示：
1?<= n <=?20000?<= dislikes.length <=?104- dislikes[i].length ==?
2 1?<= dislikes[i][j] <=?n- ai?
<?bi dislikes?中每一组都?不同
三、解题思路
首先，创建一个二维数组，用来记录1到n个数之间的互斥关系。我们以n =?10，dislikes =?[[1,2],[3,4],[5,6],[6,7],[8,9],[7,8]]为例，那么我们就可以得出如下矩阵图，如下图所示：
然后我们从第1行（row1）开始遍历，如果发现有“红色”，即表示发生了排斥，那么我们在对其进行深度遍历，如下图所示，我们遍历第1行的时候，发现2与其排斥，那么我们深度遍历第2行，由于第二行中没有与2排斥的数字了，所以我们得出结论，即：1在a组，2在b组。
我们继续遍历其他行，由于2已经被分配给了b组，所以第2行（row2）不遍历。
我们遍历第3行，由于发现与4发生了排斥，那么深度遍历到第4行，发现没有其他数组与4发生排斥，所以我们得出结论，即：3在a组，4在b组。
由于4已经被分配给了b组，所以第4行（row4）不遍历。我们遍历到第5行，发生如下遍历情况：
row5发现
数字6与它发生排斥，深度遍历到row6
row6发现数字7与它发生排斥，深度遍历到row7
row7发现数字8与它发生排斥，深度遍历到row8
row8发现数字9与它发生排斥，深度遍历到row9
row9发现没有数字与其排斥，所得得出分组结论：即：5在a组，6在b组，7在a组，8在b组，9在a组
最终结论就是，a组里有[1,3,5,7,9]?，b组里有[2,4,6,8]?，具体详情请见下图：
四、代码实现
4.1> 以二维数组方式实现矩阵
class?Solution?{
????public?boolean?possibleBipartition(int?n,?int[][]?dislikes)?{
????????int[][]?matrix?=?new?int[n?+?1][n?+?1];
????????for?(int[]?item?:?dislikes)
????????????matrix[item[0]][item[1]]?=?matrix[item[1]][item[0]]?=?1;
????????int[]?record?=?new?int[n?+?1];?//?记录分组情况
????????for?(int?i?=?1;?i?<=?n?;?i?++)
????????????if?(record[i]?==?0?&&?!?dfs(matrix,?record,?i,?1,?n))?return?false;
????????return?true;
????}
????private?boolean?dfs(int[][]?matrix,?int[]?record,?int?index,int?group,?int?n)?{
????????record[index]?=?group;
????????for?(int?i?=?1;?i?<=?n?;?i++)?{
????????????if(i?==?index?||?matrix[index][i]?==?0)?continue;
????????????if?(record[i]?==?group)?return?false;
????????????if?(record[i]?==?0?&&?!dfs(matrix,?record,?i,?group?*?-1,?n))?return?false;
????????}
????????return?true;
????}
}4.2> 以List方式进行改造
class?Solution?{
????public?boolean?possibleBipartition(int?n,?int[][]?dislikes)?{
????????List<Integer>[]?matrix?=?new?ArrayList[n?+?1];
????????for?(int?i?=?1;?i?<?matrix.length;?i++)?matrix[i]?=?new?ArrayList(n?+?1);
????????for?(int[]?item?:?dislikes)?{
????????????matrix[item[0]].add(item[1]);
????????????matrix[item[1]].add(item[0]);
????????}
????????int[]?record?=?new?int[n?+?1];?//?记录分组情况
????????for?(int?i?=?1;?i?<?matrix.length?;?i?++)
????????????if?(record[i]?==?0?&&?!dfs(matrix,?record,?i,?1))?return?false;
????????return?true;
????}
????private?boolean?dfs(List<Integer>[]?matrix,?int[]?record,?int?index,?int?group)?{
????????record[index]?=?group;
????????for?(int?i?=?0;?i?<?matrix[index].size()?;?i++)?{
????????????int?num?=?matrix[index].get(i);
????????????if?(record[num]?==?group)?return?false;
????????????if?(record[num]?==?0?&&?!dfs(matrix,?record,?num,?group?*?-1))?return?false;
????????}
????????return?true;
????}
}今天的文章内容就这些了：
写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的?点赞?&?分享?。
更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(^o^)/ ~ 「干货分享，每天更新」