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

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

题目要求

思路一:反向点+并查集

  • 根据题意不喜欢就不在一个组可以想到使用并查集,本题是两个集合所以对每一个节点引入一个反向点,使两者分属于不同集合,借此记录前续节点维持的不喜欢关系;
  • 在将每个节点xxx放入组合时,同时将其反向节点x+nx+nx+n放入另一组合,然后向后遍历依次处理每个节点,同时判断相互不喜欢的两个点当前是否会被迫放入一个集合(连通),若是则无法满足题意。

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

浅学并查集(Union Find)

学习参考链接

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

简介:

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

  • 核心思想:
    • 用一个数组表示整片森林,树的根节点唯一标识了一个集合,只要找到了某个元素的树根,就能确定它在哪个集合里;
  • 适用场景:
    • 用于需要反复查找某一元素属于哪个集合以进行集合合并的场景,用其他数据结构解决该类问题将造成巨大的时空开销。

基础操作:

通常包括三个函数

函数 功能
find(x) 查找元素xxx属于哪个集合,也就是找当前元素所在树的根节点,查找的同时进行路径压缩
union(a, b) 合并元素aaa和元素bbb所属集合,根据树高合并两棵树
isConnected(a, b) 判断aaa和元素bbb是否处于同一集合中,也就是判断二者根是否相同

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 
  • 时间复杂度: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>& dislikes) {
        for (int i = 1; i 
  • 时间复杂度: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 
  • 时间复杂度: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>& 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 
  • 时间复杂度:O(n+m)
  • 空间复杂度:O(n+m)

总结

算法题就回避一下Rust……待我学成归来……

填了拖了好久的并查集的坑还捎带复习了一波链式前向星存图;

感觉链式前向星忘得差不多了……

以上就是Java C++题解leetcode886可能的二分法并查集染色法的详细内容,更多关于Java C++ 可能的二分法的资料请关注IT俱乐部其它相关文章!

本文收集自网络,不代表IT俱乐部立场,转载请注明出处。https://www.2it.club/code/java/5005.html
上一篇
下一篇
联系我们

联系我们

在线咨询: QQ交谈

邮箱: 1120393934@qq.com

工作时间:周一至周五,9:00-17:30,节假日休息

关注微信
微信扫一扫关注我们

微信扫一扫关注我们

返回顶部