今天的力扣打卡題是「785. 判斷二分圖」，讓我們一起用「深度優先搜索」、「廣度優先搜索」、「併查集」三種不同的方法搞定它！
原題描述力扣 785. 判斷二分圖
難度：Medium
給定一個無向圖 graph，當這個圖為二分圖時返回 true。
如果我們能將一個圖的頂點集合分割成兩個獨立的子集 A 和 B，並使圖中的每一條邊的兩個頂點一個來自 A 集合，一個來自 B 集合，我們就將這個圖稱為二分圖。
graph 將會以鄰接表方式給出，graph[i] 表示圖中與頂點 i 相連的所有頂點。每個頂點都是一個在 0 到 graph.length - 1 之間的整數。
圖中沒有自環和平行邊：graph[i] 中不存在 i，並且 graph[i] 中沒有重複的值。
示例 1:：
輸入: [[1,3], [0,2], [1,3], [0,2]]
輸出: true
解釋:
無向圖如下:
0----1
| |
| |
3----2
我們可以將節點分成兩組: {0, 2} 和 {1, 3}。
示例 2:：
輸入: [[1,2,3], [0,2], [0,1,3], [0,2]]
輸出: false
解釋:
無向圖如下:
0--1
| \ |
| \ |
3--2
我們不能將節點分割成兩個獨立的子集。
若無向圖
例如上圖，頂點可以分為紅色和藍色兩個集合，且圖中每條邊的兩個頂點分別屬於不同的集合，因此 上圖是二分圖。
又如上圖，頂點無法劃分為紅色和藍色兩個集合，使得圖中每條邊的兩個頂點分別屬於不同的集合，因此 上圖不是二分圖。
我們使用圖搜索算法從各個連通域的任一頂點開始遍歷整個連通域，遍歷的過程中用兩種不同的顏色對頂點進行 染色，相鄰頂點染成相反的顏色。這個過程中倘若發現相鄰的頂點已經被染成了相同的顏色，說明它不是二分圖；反之，如果所有的連通域都染色成功，說明它是二分圖。
併查集根據定義，如果是二分圖的話，那麼 圖中每個頂點的所有鄰接點都應該屬於同一集合，且不與頂點處於同一集合。因此我們可以使用併查集來解決這個問題，我們遍歷圖中每個頂點，將當前頂點的所有鄰接點進行合併，並判斷這些鄰接點中是否存在某一鄰接點已經和當前頂點處於同一個集合中了，若是，則說明不是二分圖。
具體實現廣度優先搜索首先定義 int[] visited 數組，初始值為 0 表示未被訪問，賦值為 1 或者 -1 表示兩種不同的顏色。對於每個連通域，任選其中一個頂點作為搜索起點，加入隊列，對該連通域進行 BFS 染色，詳見注釋。class Solution {
public boolean isBipartite(int[][] graph) {
int[] visited = new int[graph.length];
Queue<Integer> queue = new LinkedList<>();
// 因為圖中可能含有多個連通域，所以我們需要判斷是否存在頂點未被訪問，若存在則從它開始再進行一輪 bfs 染色。
for (int i = 0; i < graph.length; i++) {
if (visited[i] != 0) {
continue;
}
// 每出隊一個頂點，將其所有鄰接點染成相反的顏色併入隊。
queue.offer(i);
visited[i] = 1;
while (!queue.isEmpty()) {
int v = queue.poll();
for (int w: graph[v]) {
// 如果當前頂點的某個鄰接點已經被染過色了，且顏色和當前頂點相同，說明此無向圖無法被正確染色，返回 false。
if (visited[w] == visited[v]) {
return false;
}
if (visited[w] == 0) {
visited[w] = -visited[v];
queue.offer(w);
}
}
}
}
return true;
}
}
深度優先搜索首先定義 int[] visited 數組，初始值為 0 表示未被訪問，賦值為 1 或者 -1 表示兩種不同的顏色。對於每個連通域，任選其中一個頂點作為搜索起點，對該連通域進行 DFS 染色，詳見注釋。class Solution {
public boolean isBipartite(int[][] graph) {
int[] visited = new int[graph.length];
// 因為圖中可能含有多個連通域，所以我們需要判斷是否存在頂點未被訪問，若存在則從它開始再進行一輪 dfs 染色。
for (int i = 0; i < graph.length; i++) {
if (visited[i] == 0 && !dfs(graph, i, 1, visited)) {
return false;
}
}
return true;
}
private boolean dfs(int[][] graph, int v, int color, int[] visited) {
// 如果要對某頂點染色時，發現它已經被染色了，則判斷它的顏色是否與本次要染的顏色相同，如果矛盾，說明此無向圖無法被正確染色，返回 false。
if (visited[v] != 0) {
return visited[v] == color;
}
// 對當前頂點進行染色，並將當前頂點的所有鄰接點染成相反的顏色。
visited[v] = color;
for (int w: graph[v]) {
if (!dfs(graph, w, -color, visited)) {
return false;
}
}
return true;
}
}
併查集
遍歷圖中每個頂點：
判斷是否存在鄰接點與當前頂點已經在一個集合中了，若存在，則說明不是二分圖class Solution {
public boolean isBipartite(int[][] graph) {
// 初始化併查集
UnionFind uf = new UnionFind(graph.length);
// 遍歷每個頂點
for (int i = 0; i < graph.length; i++) {
int[] adjs = graph[i];
// 遍歷當前頂點的所有鄰接點，將其與當前頂點的第一個鄰接點合併。
for (int w: adjs) {
// 若某個鄰接點與當前頂點已經在一個集合中了，說明不是二分圖，返回 false。
if (uf.isConnected(i, w)) {
return false;
}
uf.union(adjs[0], w);
}
}
return true;
}
}
上述代碼中使用的併查集定義如下：
// 併查集
class UnionFind {
int[] roots;
// 初始化每個點指向自己
public UnionFind(int n) {
roots = new int[n];
for (int i = 0; i < n; i++) {
roots[i] = i;
}
}
// 返回 i 的根
public int find(int i) {
if (roots[i] == i) {
return i;
}
return roots[i] = find(roots[i]);
}
// 判斷 p 和 q 是否在同一個集合中
public boolean isConnected(int p, int q) {
return find(q) == find(p);
}
// 合併 p 和 q 到一個集合中
public void union(int p, int q) {
roots[find(p)] = find(q);
}
}
複雜度分析上述三種方法，時間複雜度是
知識拓展導讀在二分圖上，最常見的問題是求 二分圖最大匹配/最大獨立集。二分圖的最大匹配，簡單來說就是找到儘可能多的兩兩匹配的關係。比如說在某場相親現場，主持人先讓所有男生女生都寫好自己感興趣的若干個異性，主持人需要儘可能多的湊一對對男女去約會。
這個問題經典的解法是 匈牙利算法，這塊知識超過了面試要求，感興趣的同學可以自行查閱資料。
說到相親，還有一個著名的算法叫做 穩定婚姻問題。就是說，主持人的你安排男男女女相親，如果當前是男 1 和女 2 在一起，男 2 和女 1 在一起，男1更喜歡女1，女1也更喜歡男1，那麼他倆就會私奔，你的安排相親就是 不穩定 的。對於一群男生和女生，你需要給出一個 穩定 的相親方案。這個有趣的算法，感興趣的同學可以看下 matrix67 大神對於這個故事的闡述～
什麼是算法：如何尋找穩定的婚姻搭配 http://www.matrix67.com/blog/archives/2976
題目拓展力扣 886.可能的二分法
題目描述： 給定 N 人（編號為 1, 2, ..., N），將其分為兩組。每個人都可能有不喜歡的人，那麼他們不應該屬於同一組，當可以用這種方法將這些人分為兩組時，返回 true；否則返回 false。
題目分析： 這題實質也是判斷是否構成二分圖（以每個人為頂點，以「不喜歡」為邊，即若 A 不喜歡 B，則在 A 與 B 之間建邊）。
力扣 1349. 參加考試的最大學生數
題目描述： 給定一個教室裡 n * m 的座位，裡面有一些座位是壞的不能坐。你需要安排學生的座位，要求每個學生的左上/右上/左/右都沒有其它學生。要求儘可能多的安排學生考試，問最多可以安排幾個學生。
提示： 這道題涉及到求 二分圖最大獨立集，也可以用帶狀態壓縮的動態規劃來做。
鏘鏘鏘！[✅] 今日營業完成
我的多篇題解被Leetcode官網評為 「精選題解」
大佬們可以隨手關注一下我的知乎專欄 「甜姨的力扣題解」
寶寶們快快快 三連（點讚 + 在看 + 轉發）鴨 ٩(●˙ε˙●)۶
關注甜姨不迷路！
帶你刷穿各類題目不是夢！<(￣ˇ￣)/