染色法/二分法一、题目二、染色法三、代码

116 阅读 0 评论 77 点赞

我是靠谱客的博主神勇便当，最近开发中收集的这篇文章主要介绍染色法/二分法一、题目二、染色法三、代码，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

一、题目

给定一组 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]

也就是说在dislike数组中有边的两个结点不能放在同一组里，两个组中不能存在边

二、染色法

一个n个结点，从第一个结点，先将它染成蓝色（1），再根据其含有的边将不能放在一组内的结点染成红色（2），color数组初始值为无色（0）。

根据示例1，1的排斥点为2，3，相应地，2和3也排斥1。

首先将dislikes数组转化成每个点对应的所有排斥点，即g = [[2,3],[1,4],[1],[2]] (在代码中由于数组下标从0开始所以相应的将结点-1)。

然后根据g数组，从1开始染色，这样的话如果在染色2、3、4时，如果发现新的染色与前面的染色冲突时，return False，没有冲突则默认return True。

三、代码

class Solution:
def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
temp=[[] for x in range(n)]
for x,y in dislikes:
temp[x-1].append(y-1)
temp[y-1].append(x-1)
color = [0] *n
def dfs(i: int, c: int) -> bool:
color[i] = c
# 冲突检测
for j in temp[i]:
if color[j] == c:
return False
elif color[j] == 0 and not dfs(j, 3-c):# j为染色and将j点染色时出现冲突
return False
return True
return all(c or dfs(i, 1) for i, c in enumerate(color))

temp为转换数组，根据dislikes将每个结点排斥的点进行统计，此处需要注意的是，一个边如[1,2]包含两个结点，1排斥2，2也排斥1，所以需要在两个点的排斥点中都添加对方。

color为染色数组，记录每个点的染色情况。

使用深度优先遍历，i为结点，c是染的颜色，c=0为未染色，c=1为蓝色，c=2为红色。

首先将i染成c色，根据temp数组，如果i点排斥的j点已经染成与i相同的c色，说明冲突了，就False；如果没染色，把j点染成另一种颜色（3-c），如果检测到冲突，也False。如果都没有，return True。

all()：检测给定的列表字典等是否为False（空）。

注：最后一句的意思是，根据color数组，如果c=0，即未染色的话，则默认将i点染成1色，检测有无冲突并输出，如果c!=0的话，说明i点已经染色了，那么由于or的性质，此时判断式结果已经为True，则不执行or后面的dfs函数，不会再染色了！