Java C++题解leetcode886可能的二分法并查集染色法

题目要求

思路一：反向点+并查集

• 根据题意不喜欢就不在一个组可以想到使用并查集，本题是两个集合所以对每一个节点引入一个反向点，使两者分属于不同集合，借此记录前续节点维持的不喜欢关系；

• 在将每个节点xxx放入组合时，同时将其反向节点x+nx+nx+n放入另一组合，然后向后遍历依次处理每个节点，同时判断相互不喜欢的两个点当前是否会被迫放入一个集合（连通），若是则无法满足题意。

下面浅学一些并查集的基本概念，然后再去实现思路——

浅学并查集（Union Find）

学习参考链接

• 从介绍到不断优化的整个构造推导过程，图片示例与解释很清晰。

简介：

一种树型的数据结构，用于处理一些不相交集合的合并及查询问题；

• 核心思想：

• 用一个数组表示整片森林，树的根节点唯一标识了一个集合，只要找到了某个元素的树根，就能确定它在哪个集合里；

• 适用场景：

• 用于需要反复查找某一元素属于哪个集合以进行集合合并的场景，用其他数据结构解决该类问题将造成巨大的时空开销。

基础操作：

通常包括三个函数

Java

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 <= 2 * n; i++) // 节点+反向节点
           p[i] = i; // 初始化并查集，指向自己
       for (int[] cur : dislikes) {
           int a = cur[0], b = cur[1];
           if (isConnected(a, b)) // 连通，被迫在一组
               return false;
           // 利用反向节点维护连通关系
           union(a, b + n);
           union(b, a + n);
       }
       return true;
   }
}

• 时间复杂度：O(n+m)，其中m为dislikes的长度

• 空间复杂度：O(n)

C++

• 注意union会和C++中的预定义函数重名

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<int>>& dislikes) {
       for (int i = 1; i <= 2 * n; i++) // 节点+反向节点
           p[i] = i; // 初始化并查集，指向自己
       for (auto cur : dislikes) {
           int a = cur[0], b = cur[1];
           if (isConnected(a, b)) // 连通，被迫在一组
               return false;
           // 利用反向节点维护连通关系
           unionn(a, b + n);
           unionn(b, a + n);
       }
       return true;
   }
};

• 时间复杂度：O(n+m)

• 空间复杂度：O(n)

思路二：染色法

• 将不喜欢数组存成一个无向图，给分属两个不同集合的点染上不同的颜色，不断更新染色并判断不喜欢关系是否能够成立；

• 采用链式前向星存储构建无向图，有边的两者不能是同一个颜色，用1和2表示两种不同的颜色，用000表示未染色；

• 定义一个DFS(node, clr)函数表示将节点node染成clr色

Java

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 <= n; i++) {
           if (color[i] != 0) // 已经染过
               continue;
           if (!DFS(i, 1)) // 无法染色成功
               return false;
       }
       return true;
   }
}

• 时间复杂度：O(n+m)

• 空间复杂度：O(n+m)

C++

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<int>>& 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 <= n; i++) {
           if (color[i] != 0) // 已经染过
               continue;
           if (!DFS(i, 1)) // 无法染色成功
               return false;
       }
       return true;
   }
};

• 时间复杂度：O(n+m)

• 空间复杂度：O(n+m)

来源：https://juejin.cn/post/7155034629202771998