题目描述
这是 力扣上的 886. 可能的二分法，难度为 中等。
题目分析
题目中给出 n 个人，编号分别是 1...n ，和一个 dislikes 二维数组，表示的意思是，a 讨厌 b，b 也讨厌 a，是不能放到同一组的
现在要我们将 n 个人分成 2 组，要我们确认这 n 个人是否可以顺利的分成 2 组
看到这个题目，我一下子会想到跟着旅行团住酒店时候的场景，男-男 ， 女-女，落单的自己付双份
不过咱们这个题还没有那么容易
思考：
不过这个题也不麻烦，只是需要我们思考清楚
题目给出的 dislikes 二维数组，很明显我们是可以做一个无向图，表示 a 讨厌哪些人，例如有 b，c，d，那么对于 b 就有 讨厌 a 和 其他人，例如示例 1 中的这样，
- 1 讨厌 2, 3
- 2 讨厌 1, 4
- 3 讨厌 1
- 4 讨厌 2
| 1 | 2 | 3 |
| 2 | 1 | 4 |
| 3 | 1 | |
| 4 | 2 |
另外题目中要求我们将这 n 个人分为两组，那么咱们就可以设置 3 种状态，并且把这三种状态放到一个数组中，记为 color ，数组索引对应的值表示状态
- 0 表示未访问
- 1 表示放到第 1 组
- 2 表示放到第 2 组
那么，这个时候，我们应该如何来处理呢？
我们这样来思考，咱们的 color 数组，最开始肯定是全 0 的，因为还没有进行访问过任何一个人，如果访问结束且顺利的话，color 数组是每一个位置上都会有一个确定的数字，要么 1 ，要么 2，当然这是我们期望顺利的情况，如果不顺利的话，那么就没有办法正常分为 2 组了
现在有了无向图，有了记录状态的 color，实际上，我们就可以来进行遍历 color 数组，来对每一个人来分组了
使用深度优先的方式来进行分组，遍历 color 数组，如果发现当前这个人是未分组的（即 0） ，则默认分组到 1 组，并且要确认这个人对应不喜欢的人，必须要全部分组到 2 组，如果不能全部都这样分组，那么就是有冲突，则直接返回 false
同理，如果一个人被分组到 2 组，那么我们也要是确认他讨厌的所有人，都必须要分组到 1 组
那么，对于一个人当前若是 分组到 1 组的，那么我们如何将他不喜欢的人分组到 2 组呢？
此处实现也比较简单，第一种方式就是进行简单的判断，如果 a 分组到 1 组，那么他不喜欢的就分组到 2 组
我们也可以使用异或的方式来进行处理，例如当前 a 分组到 1 组，那么他不喜欢的人就分组到 3^1 = 2组，同理如果 a 分组到 2 组，那么他不喜欢的人就分组到 3^2 = 1 组
接下来，咱们就可以来实现编码了，咱们这次使用 golang 的方式来进行实现
Golang 的实现方式：
- 先做好自己的无向图，实现中，一般咱们数组的索引是从 0 开始，因此，我们可以对于人的编号也可以从 0 开始
- 定义好状态 color 数组，然后对 color 数组进行遍历，处理好 color 数组的 0,1,2 三种状态即可
- 简单思想，确认一个人被明确分到 1组，那么他不喜欢的人就必须全部分配到 2组，反之亦然
func possibleBipartition(n int, dislikes [][]int) bool { // 自己做一个无向图 help := make([][]int, n) for _,v := range dislikes { // 此处我们让 help 中的数据可以从 0 开始，而不是从 1 开始 x,y := v[0]-1, v[1]-1 help[x] = append(help[x], y) help[y] = append(help[y], x) } // 构建染色，color 数组中， 0 表示未访问，1表示红色，2表示蓝色 color := make([]int, n) var dfs func(pos, c int) bool dfs = func(pos, c int) bool { color[pos] = c // 开始去根据 pos 去找无向图中的关联项 for _,v := range help[pos]{ // 不满足的情况，如果无向图中有人和当前的 pos 是同一组，那么就冲突了 // 或者 无向图中自己讨厌的这个人，不能分到对面组，那么也是冲突了 if color[v] == c || (color[v] == 0 && !dfs(v, 3^c)){ return false } } return true } // 使用深度优先的方式去找到与当前节点相关的节点是否都能正常分配 for i := range color { // 一开始，我们发现一个人是没有访问的，那么默认分到第 1 组 if color[i] == 0 && !dfs(i, 1) { return false } } return true }
这种实现方式，咱们的时间复杂度是 O(n+m)，空间复杂度是 O(n+m)，其中 n 都是题目中给定的人数 n，其中 m 是 dislikes 数组的长度
今天就到这里，若有偏差，还请斧正
欢迎点赞，关注，收藏
朋友们，你的支持和鼓励，是我坚持分享，提高质量的动力
好了，本次就到这里
技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。
我是阿兵云原生，欢迎点赞关注收藏，下次见~
