题目要求
思路一：反向点+并查集
- 根据题意不喜欢就不在一个组可以想到使用并查集，本题是两个集合所以对每一个节点引入一个反向点，使两者分属于不同集合，借此记录前续节点维持的不喜欢关系；
- 在将每个节点xxx放入组合时，同时将其反向节点x+nx+nx+n放入另一组合，然后向后遍历依次处理每个节点，同时判断相互不喜欢的两个点当前是否会被迫放入一个集合（连通），若是则无法满足题意。
下面浅学一些并查集的基本概念，然后再去实现思路——
浅学并查集（Union Find）
- 从介绍到不断优化的整个构造推导过程，图片示例与解释很清晰。
简介：
一种树型的数据结构，用于处理一些不相交集合的合并及查询问题；
- 核心思想：
- 用一个数组表示整片森林，树的根节点唯一标识了一个集合，只要找到了某个元素的树根，就能确定它在哪个集合里；
- 适用场景：
- 用于需要反复查找某一元素属于哪个集合以进行集合合并的场景，用其他数据结构解决该类问题将造成巨大的时空开销。
基础操作：
通常包括三个函数
| 函数 | 功能 |
|---|---|
| find(x) | 查找元素xxx属于哪个集合，也就是找当前元素所在树的根节点，查找的同时进行路径压缩 |
| union(a, b) | 合并元素aaa和元素bbb所属集合，根据树高合并两棵树 |
| isConnected(a, b) | 判断aaa和元素bbb是否处于同一集合中，也就是判断二者根是否相同 |
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | class Solution { int[] p = new int[4010]; // 并查集数组，存父级节点 // 找当前节点的根 int find(int x) { if(p[x] != x) // 非根节点 p[x] = find(p[x]); // 继续向下找根并进行路径压缩 return p[x]; } // 连接两节点的根 void union(int a, int b) { p[find(a)] = p[find(b)]; } // 两节点是否连通 boolean isConnected(int a, int b) { return find(a) == find(b); } public boolean possibleBipartition(int n, int[][] dislikes) { for (int i = 1; i |
- 时间复杂度：O(n+m)，其中m为dislikes的长度
- 空间复杂度：O(n)
C++
- 注意
union会和C++中的预定义函数重名
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | class Solution {public: int p[4010]; // 并查集数组，存父级节点 // 找当前节点的根 int find(int x) { if(p[x] != x) // 非根节点 p[x] = find(p[x]); // 继续向下找根并进行路径压缩 return p[x]; } // 连接两节点的根 void unionn(int a, int b) { p[find(a)] = p[find(b)]; } // 两节点是否连通 bool isConnected(int a, int b) { return find(a) == find(b); } bool possibleBipartition(int n, vector<vector>>& dislikes) { for (int i = 1; i </vector> |
- 时间复杂度：O(n+m)
- 空间复杂度：O(n)
思路二：染色法
- 将不喜欢数组存成一个无向图，给分属两个不同集合的点染上不同的颜色，不断更新染色并判断不喜欢关系是否能够成立；
- 采用链式前向星存储构建无向图，有边的两者不能是同一个颜色，用1和2表示两种不同的颜色，用000表示未染色；
- 定义一个
DFS(node, clr)函数表示将节点node染成clr色
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 | class Solution { int N = 2010, M = 2 * 10010; int[] head = new int[N], edge = new int[M], next = new int[M]; int[] color = new int[N]; int idx = 0;; void add(int a, int b) { edge[idx] = b; next[idx] = head[a]; head[a] = idx++; } boolean DFS(int node, int clr) { color[node] = clr; for (int i = head[node]; i != -1; i = next[i]) { int j = edge[i]; // 不喜欢双方同色 if (color[j] == clr) return false; if (color[j] == 0 && !DFS(j, 3 - clr)) return false; } return true; } public boolean possibleBipartition(int n, int[][] dislikes) { Arrays.fill(head, -1); for (int[] cur : dislikes) { // 构建无向图 int a = cur[0], b = cur[1]; add(a, b); add(b, a); } for (int i = 1; i |
- 时间复杂度：O(n+m)
- 空间复杂度：O(n+m)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 | class Solution {public: static const int N = 2010, M = 2 * 10010; int head[N], edge[M], next[M]; int color[N]; int idx = 0;; void add(int a, int b) { edge[idx] = b; next[idx] = head[a]; head[a] = idx++; } bool DFS(int node, int clr) { color[node] = clr; for (int i = head[node]; i != -1; i = next[i]) { int j = edge[i]; // 不喜欢双方同色 if (color[j] == clr) return false; if (color[j] == 0 && !DFS(j, 3 - clr)) return false; } return true; } bool possibleBipartition(int n, vector<vector>>& dislikes) { memset(head, -1, sizeof(head)); for (auto cur : dislikes) { // 构建无向图 int a = cur[0], b = cur[1]; add(a, b); add(b, a); } for (int i = 1; i </vector> |
- 时间复杂度：O(n+m)
- 空间复杂度：O(n+m)
总结
算法题就回避一下Rust……待我学成归来……
填了拖了好久的并查集的坑还捎带复习了一波链式前向星存图；
感觉链式前向星忘得差不多了……
以上就是Java C++题解leetcode886可能的二分法并查集染色法的详细内容，更多关于Java C++ 可能的二分法的资料请关注IT俱乐部其它相关文章！
