Java C++題解leetcode886可能的二分法并查集染色法
更新時間：2022年10月17日 10:23:37 作者：AnjaVon
這篇文章主要為大家介紹了Java C++題解leetcode886可能的二分法并查集染色法實現示例，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪
題目要求
思路一：反向點+并查集
- 根據題意不喜歡就不在一個組可以想到使用并查集，本題是兩個集合所以對每一個節(jié)點引入一個反向點，使兩者分屬于不同集合，借此記錄前續(xù)節(jié)點維持的不喜歡關系；
- 在將每個節(jié)點xxx放入組合時，同時將其反向節(jié)點x+nx+nx+n放入另一組合，然后向后遍歷依次處理每個節(jié)點，同時判斷相互不喜歡的兩個點當前是否會被迫放入一個集合（連通），若是則無法滿足題意。
下面淺學一些并查集的基本概念，然后再去實現思路——
淺學并查集（Union Find）
- 從介紹到不斷優(yōu)化的整個構造推導過程，圖片示例與解釋很清晰。
簡介：
一種樹型的數據結構，用于處理一些不相交集合的合并及查詢問題；
- 核心思想：
- 用一個數組表示整片森林，樹的根節(jié)點唯一標識了一個集合，只要找到了某個元素的樹根，就能確定它在哪個集合里；
- 適用場景：
- 用于需要反復查找某一元素屬于哪個集合以進行集合合并的場景，用其他數據結構解決該類問題將造成巨大的時空開銷。
基礎操作：
通常包括三個函數
| 函數 | 功能 |
|---|---|
| find(x) | 查找元素xxx屬于哪個集合，也就是找當前元素所在樹的根節(jié)點，查找的同時進行路徑壓縮 |
| union(a, b) | 合并元素aaa和元素bbb所屬集合，根據樹高合并兩棵樹 |
| isConnected(a, b) | 判斷aaa和元素bbb是否處于同一集合中，也就是判斷二者根是否相同 |
Java
class Solution {
int[] p = new int[4010]; // 并查集數組，存父級節(jié)點
// 找當前節(jié)點的根
int find(int x) {
if(p[x] != x) // 非根節(jié)點
p[x] = find(p[x]); // 繼續(xù)向下找根并進行路徑壓縮
return p[x];
}
// 連接兩節(jié)點的根
void union(int a, int b) {
p[find(a)] = p[find(b)];
}
// 兩節(jié)點是否連通
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é)點+反向節(jié)點
p[i] = i; // 初始化并查集，指向自己
for (int[] cur : dislikes) {
int a = cur[0], b = cur[1];
if (isConnected(a, b)) // 連通，被迫在一組
return false;
// 利用反向節(jié)點維護連通關系
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]; // 并查集數組，存父級節(jié)點
// 找當前節(jié)點的根
int find(int x) {
if(p[x] != x) // 非根節(jié)點
p[x] = find(p[x]); // 繼續(xù)向下找根并進行路徑壓縮
return p[x];
}
// 連接兩節(jié)點的根
void unionn(int a, int b) {
p[find(a)] = p[find(b)];
}
// 兩節(jié)點是否連通
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é)點+反向節(jié)點
p[i] = i; // 初始化并查集，指向自己
for (auto cur : dislikes) {
int a = cur[0], b = cur[1];
if (isConnected(a, b)) // 連通，被迫在一組
return false;
// 利用反向節(jié)點維護連通關系
unionn(a, b + n);
unionn(b, a + n);
}
return true;
}
};
- 時間復雜度：O(n+m)
- 空間復雜度：O(n)
思路二：染色法
- 將不喜歡數組存成一個無向圖，給分屬兩個不同集合的點染上不同的顏色，不斷更新染色并判斷不喜歡關系是否能夠成立；
- 采用鏈式前向星存儲構建無向圖，有邊的兩者不能是同一個顏色，用1和2表示兩種不同的顏色，用000表示未染色；
- 定義一個
DFS(node, clr)函數表示將節(jié)點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)
總結
算法題就回避一下Rust……待我學成歸來……
填了拖了好久的并查集的坑還捎帶復習了一波鏈式前向星存圖；
感覺鏈式前向星忘得差不多了……
以上就是Java C++題解leetcode886可能的二分法并查集染色法的詳細內容，更多關于Java C++ 可能的二分法的資料請關注腳本之家其它相關文章！
相關文章
有時我們希望將把數據保存在單個連續(xù)的數組中,以便快速、便捷地訪問數據,但這需要調整數組大小或者對其擴展,下面這篇文章主要給大家介紹了關于Java自定義一個變長數組的思路與代碼,需要的朋友可以參考下2022-12-12
這篇文章主要介紹了Java反射技術原理與用法,結合實例形式分析了Java反射技術的基本概念、功能、原理、用法及操作注意事項,需要的朋友可以參考下2021-07-07
這篇文章主要介紹了Java基于中介者模式實現多人聊天室功能,詳細分析了中介者模式的概念、原理以及使用中介模式實現多人聊天的步驟、操作技巧與注意事項,需要的朋友可以參考下2018-05-05
這篇文章主要為大家詳細介紹了java獲取本月日歷表的方法，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-06-06
MVC是一種軟件設計典范，用一種業(yè)務邏輯、數據、界面顯示分離的方法組織代碼，將業(yè)務邏輯聚集到一個組件里面，在改進和個性化定制界面及用戶交互的同時，不需要重新編寫業(yè)務邏輯，MVC分層有助于管理和架構復雜的應用程序2021-06-06
這篇文章主要介紹了String類型如何轉換為time類型存進數據庫，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-03-03
與其明天開始，不如現在行動，本文為你帶來幾個Java書寫的實際案例，對鞏固編程的基礎能力很有幫助，快來一起往下看看吧2022-03-03
這篇文章主要介紹了Java爬蟲(Jsoup與WebDriver)的使用,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2020-12-12
下面小編就為大家?guī)硪黄獪\談Java double 相乘的結果偏差小問題。小編覺得挺不錯的，現在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-01-01
在Java中發(fā)送form-data請求,可以使用Apache?HttpClient或OkHttp這樣的HTTP客戶端庫來發(fā)送請求,本文通過實例代碼給大家介紹的非常詳細,對大家的學習或工作具有一定的參考借鑒價值,需要的朋友參考下吧2023-10-10