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

更新時(shí)間：2022年10月17日 10:23:37 作者：AnjaVon

這篇文章主要為大家介紹了Java C++題解leetcode886可能的二分法并查集染色法實(shí)現(xiàn)示例，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪

題目要求

思路一：反向點(diǎn)+并查集

根據(jù)題意不喜歡就不在一個(gè)組可以想到使用并查集，本題是兩個(gè)集合所以對(duì)每一個(gè)節(jié)點(diǎn)引入一個(gè)反向點(diǎn)，使兩者分屬于不同集合，借此記錄前續(xù)節(jié)點(diǎn)維持的不喜歡關(guān)系；
在將每個(gè)節(jié)點(diǎn)xxx放入組合時(shí)，同時(shí)將其反向節(jié)點(diǎn)x+nx+nx+n放入另一組合，然后向后遍歷依次處理每個(gè)節(jié)點(diǎn)，同時(shí)判斷相互不喜歡的兩個(gè)點(diǎn)當(dāng)前是否會(huì)被迫放入一個(gè)集合（連通），若是則無法滿足題意。

下面淺學(xué)一些并查集的基本概念，然后再去實(shí)現(xiàn)思路——

淺學(xué)并查集（Union Find）

學(xué)習(xí)參考鏈接

從介紹到不斷優(yōu)化的整個(gè)構(gòu)造推導(dǎo)過程，圖片示例與解釋很清晰。

簡(jiǎn)介：

一種樹型的數(shù)據(jù)結(jié)構(gòu)，用于處理一些不相交集合的合并及查詢問題；

核心思想：
- 用一個(gè)數(shù)組表示整片森林，樹的根節(jié)點(diǎn)唯一標(biāo)識(shí)了一個(gè)集合，只要找到了某個(gè)元素的樹根，就能確定它在哪個(gè)集合里；
適用場(chǎng)景：
- 用于需要反復(fù)查找某一元素屬于哪個(gè)集合以進(jìn)行集合合并的場(chǎng)景，用其他數(shù)據(jù)結(jié)構(gòu)解決該類問題將造成巨大的時(shí)空開銷。

基礎(chǔ)操作：

通常包括三個(gè)函數(shù)

函數(shù)	功能
find(x)	查找元素xxx屬于哪個(gè)集合，也就是找當(dāng)前元素所在樹的根節(jié)點(diǎn)，查找的同時(shí)進(jìn)行路徑壓縮
union(a, b)	合并元素aaa和元素bbb所屬集合，根據(jù)樹高合并兩棵樹
isConnected(a, b)	判斷aaa和元素bbb是否處于同一集合中，也就是判斷二者根是否相同

Java

class Solution {
    int[] p = new int[4010]; // 并查集數(shù)組，存父級(jí)節(jié)點(diǎn)
    // 找當(dāng)前節(jié)點(diǎn)的根
    int find(int x) {
        if(p[x] != x) // 非根節(jié)點(diǎn)
            p[x] = find(p[x]); // 繼續(xù)向下找根并進(jìn)行路徑壓縮
        return p[x];
    }
    // 連接兩節(jié)點(diǎn)的根
    void union(int a, int b) {
        p[find(a)] = p[find(b)];
    }
    // 兩節(jié)點(diǎn)是否連通
    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++) // 節(jié)點(diǎn)+反向節(jié)點(diǎn)
            p[i] = i; // 初始化并查集，指向自己
        for (int[] cur : dislikes) {
            int a = cur[0], b = cur[1];
            if (isConnected(a, b)) // 連通，被迫在一組
                return false;
            // 利用反向節(jié)點(diǎn)維護(hù)連通關(guān)系
            union(a, b + n);
            union(b, a + n);
        }
        return true;
    }
}

時(shí)間復(fù)雜度：O(n+m)，其中m為dislikes的長(zhǎng)度
空間復(fù)雜度：O(n)

C++

注意union會(huì)和C++中的預(yù)定義函數(shù)重名

class Solution {
public:
    int p[4010]; // 并查集數(shù)組，存父級(jí)節(jié)點(diǎn)
    // 找當(dāng)前節(jié)點(diǎn)的根
    int find(int x) {
        if(p[x] != x) // 非根節(jié)點(diǎn)
            p[x] = find(p[x]); // 繼續(xù)向下找根并進(jìn)行路徑壓縮
        return p[x];
    }
    // 連接兩節(jié)點(diǎn)的根
    void unionn(int a, int b) {
        p[find(a)] = p[find(b)];
    }
    // 兩節(jié)點(diǎn)是否連通
    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++) // 節(jié)點(diǎn)+反向節(jié)點(diǎn)
            p[i] = i; // 初始化并查集，指向自己
        for (auto cur : dislikes) {
            int a = cur[0], b = cur[1];
            if (isConnected(a, b)) // 連通，被迫在一組
                return false;
            // 利用反向節(jié)點(diǎn)維護(hù)連通關(guān)系
            unionn(a, b + n);
            unionn(b, a + n);
        }
        return true;
    }
};

時(shí)間復(fù)雜度：O(n+m)
空間復(fù)雜度：O(n)

思路二：染色法

將不喜歡數(shù)組存成一個(gè)無向圖，給分屬兩個(gè)不同集合的點(diǎn)染上不同的顏色，不斷更新染色并判斷不喜歡關(guān)系是否能夠成立；
采用鏈?zhǔn)角跋蛐谴鎯?chǔ)構(gòu)建無向圖，有邊的兩者不能是同一個(gè)顏色，用1和2表示兩種不同的顏色，用000表示未染色；
定義一個(gè)DFS(node, clr)函數(shù)表示將節(jié)點(diǎn)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) { // 構(gòu)建無向圖
            int a = cur[0], b = cur[1];
            add(a, b);
            add(b, a);
        }
        for (int i = 1; i <= n; i++) {
            if (color[i] != 0) // 已經(jīng)染過
                continue;
            if (!DFS(i, 1)) // 無法染色成功
                return false;
        }
        return true;
    }
}

時(shí)間復(fù)雜度：O(n+m)
空間復(fù)雜度：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) { // 構(gòu)建無向圖
            int a = cur[0], b = cur[1];
            add(a, b);
            add(b, a);
        }
        for (int i = 1; i <= n; i++) {
            if (color[i] != 0) // 已經(jīng)染過
                continue;
            if (!DFS(i, 1)) // 無法染色成功
                return false;
        }
        return true;
    }
};