Q886PossibleBipartition
题目简介
给定一组 n 人（编号为 1, 2, …, n）， 我们想把每个人分进任意大小的两组。每个人都可能不喜欢其他人，那么他们不应该属于同一组。
给定整数 n 和数组 dislikes ，其中 dislikes[i] = [ai, bi] ，表示不允许将编号为 ai 和 bi 的人归入同一组。当可以用这种方法将所有人分进两组时，返回 true ；否则返回 false 。
示例 1：
输入：n = 4, dislikes = [ [1,2],[1,3],[2,4] ]
输出：true
解释：group1 [ 1,4 ], group2 [ 2,3 ]
示例 2：
输入：n = 3, dislikes = [ [1,2],[1,3],[2,3] ]
输出：false
示例 3：
输入：n = 5, dislikes = [ [1,2],[2,3],[3,4],[4,5],[1,5] ]
输出：false
https://leetcode.cn/problems/possible-bipartition
解题思路
着色法，假设第一组的人是红色，第二组的人是蓝色，有以下推论，一个人是红色的，那他不喜欢的人就都是蓝色的，即所有不喜欢红色的人都是蓝色的，所有不喜欢蓝色的人都是红色的。
如果在着色的过程中有冲突那就是false，没有冲突，所有人着色完毕，那就是true。
从任一个人开始，先给他着红色，然后把他所有不喜欢的人着蓝色，在把不喜欢人的不喜欢的人再着红色，即深度优先遍历，每次着色前判断是否已经着色和所着颜色是否正确即可。
代码
public class Q886PossibleBipartition {
ArrayList[] adjList;
Map colorMap;
public boolean possibleBipartition(int n, int[][] dislikes) {
adjList = new ArrayList[n + 1];
for (int i = 0; i (); //初始化邻接表
}
for (int[] dislike : dislikes) {
adjList[dislike[0]].add(dislike[1]); //填充邻接表
adjList[dislike[1]].add(dislike[0]);
}
colorMap = new HashMap<>();
for (int i = 1; i
测试
public class Q886PossibleBipartitionTest {
public Q886PossibleBipartition q = new Q886PossibleBipartition();
@Test
public void test1() {
assertTrue(q.possibleBipartition(4, new int[][]{{1,2},{1,3},{2,4}}));
}
@Test
public void test2() {
assertFalse(q.possibleBipartition(3, new int[][]{{1,2}, {1,3},{2,3}}));
}
@Test
public void test3() {
assertFalse(q.possibleBipartition(5, new int[][]{{1,2},{2,3},{3,4},{4,5},{1,5}}));
}
}
提交结果
Original: https://www.cnblogs.com/mrystar/p/16584025.html
Author: Mr耀
Title: 力扣|Q886可能的二分法PossibleBipartition
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/586249/
转载文章受原作者版权保护。转载请注明原作者出处！